In the (1-dimensional) bin packing problem, we are asked to pack all the given items into bins, each of capacity one, so that the number of non-empty bins is minimized. Zhu [Chaos, Solitons & Fractals 2016] proposed an approximation algorithm MM that sorts the item sequence in a non-increasing order by size at the beginning, and then repeatedly packs, into the current single open bin, first as many of the largest items in the remaining sequence as possible and then as many of the smallest items in the remaining sequence as possible. In this paper we prove that the asymptotic approximation ratio of MM is at most 1.5. Next, focusing on the fact that MM is at the intersection of two algorithm classes, max-min algorithms and 1-bounded space algorithms, we comprehensively analyze the theoretical performance bounds of each subclass derived from the two classes. Our results include a lower bound of 1.25 for the intersection of the two classes. Furthermore, we extend the theoretical analysis over algorithm classes to the cardinality constrained bin packing problem.

With the rapid proliferation of various cloud storage services in recent years, the development of technology to efficiently search data while ensuring its confidentiality during cloud usage is an important issue. The technology that enables keyword searches on encrypted files using previously set keywords is called searchable symmetric encryption (SSE). In this paper, we propose a method formally representing encrypted document, and verify the security of SSE using the formal verification tool ProVerif. Our proposed method considers the channel-type terms of ProVerif as a Document that includes different keywords to verify the indistinguishability of encrypted documents.

As the scale and complexity of cloud systems are increasing, system faults are becoming unavoidable. Therefore, they should be detected as reliably and accurately as possible. Black-box monitoring can reliably monitor a target system from a remote host, but it is often coarse-grained and cannot identify the root causes of system faults. In contrast, white-box monitoring can accurately obtain fault information inside a target system, but it is largely affected by system faults. This paper proposes GPUSentinel for more reliable white-box monitoring using general-purpose GPUs. GPUSentinel runs fault detectors in an isolated GPU, which is not easily affected by faults of a target system. For accurate detection, fault detectors in a GPU analyze main memory and directly monitor the state of the operating system. To easily develop such fault detectors, GPUSentinel provides a development environment with LLVM. We have implemented GPUSentinel and seven fault detectors and then confirmed that GPUSentinel could detect various system faults and identify the root causes.

This paper describes a method for extracting character strings from scene images. Most characters on scene images appear with the same color and font size at every word or text line. In our algorithm, a scene image is divided into several blocks based on edges in the color space at first. Then the blobs, which consist of similar color pixels, are extracted by a clustering in a color space for each block. Although these blobs are correspond to characters or background patterns, after connecting them using these aspect ratios and pitches, SVM (Support Vector Machine) on several textural features of these blobs will classify each connected blob into character or background patterns. Testing with 251 images from ICDAR 2003 Text Locating Competition shows effectiveness of our algorithm.

A new electrostatic tactile display is proposed to realize compact tactile display devices that can be incorporated with virtual reality systems. The tactile display of this study consists of a thin conductive film slider with stator electrodes that excite electrostatic forces. Users of the device experience tactile texture sensations by moving the slider with their fingers. The display operates by applying two-phase cyclic voltage patterns to the electrodes. The display is incorporated into a tactile telepresentation system to realize explorations of remote surface textures with real-time tactile feedback. In the system, a PVDF tactile sensor and a DSP controller automatically generate voltage patterns to present surface texture sensations through the tactile display. A sensor, in synchronization with finger motion on the tactile display, scans a texture sample and outputs information about the sample surface. The information is processed by a DSP and fed back to the tactile display in real time. The tactile telepresentation system was evaluated in texture discrimination tests and demonstrated a 79 percent correct answer ratio. A transparent electrostatic tactile display is also reported in which the tactile display is combined with an LCD to realize a visual-tactile integrated display system.

A new electrostatic tactile display is proposed to realize compact tactile display devices that can be incorporated with virtual reality systems. The tactile display of this study consists of a thin conductive film slider with stator electrodes that excite electrostatic forces. Users of the device experience tactile texture sensations by moving the slider with their fingers. The display operates by applying two-phase cyclic voltage patterns to the electrodes. This paper reports on the application of the new tactile display in a tactile tele-presentation system. In the system, a PVDF tactile sensor and DSP controller automatically generate voltage patterns to present surface texture sensations through the tactile display. A sensor, in synchronization with finger motion on the tactile display, scans a texture sample and outputs information about the sample surface. The information is processed by a DSP and fed back to the tactile display in real time. The tactile tele-presentation system was evaluated in texture discrimination tests and demonstrated a 79% correct answer ratio. A transparent electrostatic tactile display is also reported in which the tactile display is combined with an LCD to realize a visual-tactile integrated display system.

Recently we proposed the stochastic sampling method (SSM), which can numerically generate sample points on complicated implicit surfaces quickly and uniformly. In this paper we generalize the method in two aspects: (1) We introduce two kinds of boundary conditions, so that we can sample a finite part of an open surface spreading infinitely. (2) We generalize the stochastic differential equation used in the SSM, so that its solutions can satisfy plural constraint conditions simultaneously. The first generalization enables us to visualize cut views of open surfaces. The second generalization enables us to visualize intersections of static and moving implicit surfaces, which leads to detailed investigation of intersections and other interesting applications such as visualization of contour maps.