We propose a compact and efficient index structure for massive data sets. Several indexing techniques are widely-used and well-known such as binary trees and B+trees. Unfortunately, we find that these techniques suffer major two shortcomings when applied to massive sets; first, their indices are so large they could overflow regular main memory, and, second, they suffer from a variety of penalties (e.g., conditional branches, low cache hits, and TLB misses), which restricts the number of instructions executed per processor cycle. Our state-of-the-art index structure, called VAST-Tree, classifies branch nodes into multiple layers. It applies existing techniques such as cache-conscious, aligned, and branch-free structures to the top layers of branch nodes in trees. Next, it applies the adaptive compression technique to save space and harness data parallelism with SIMD instructions to the middle and bottom layers of branch nodes. Moreover, a processor-friendly compression technique is applied to leaf nodes. The end result is that trees are much more compact and traversal efficiency is high. We implement a prototype and show its resulting index size and performance as compared to binary trees, and the hardware-conscious technique called FAST which currently offers the highest performance. Compared to current alternatives, VAST-Tree compacts the branch nodes by more than 95%, and the overall index size by 47-84% given that there are 230 keys. With 228 keys, it has roughly 6.0-times and 1.24-times throughput and saves the memory consumption by more than 94.7% and 40.5% as compared to binary trees and FAST, respectively.

There are a variety of media processing parts such as Image-Magick, FFmpeg, and OpenCV. A mechanism is necessary that allows PC users to access easily these parts in a cloud. We propose Polder, a programming environment based on a simple processing principle that provides novices with an easy programming and execution environment. Data input is achieved through dragging and dropping data objects onto a folder. The input data object is processed by a program bound to the folder name and the resulting data object is stored in the same folder. Establishing a hierarchical folder structure chains the processes of the folders. Combined with a WebDAV network folder, Polder becomes a mashup environment for end users. In this paper, we evaluate and discuss Polder based on a user questionnaire administered after students test Polder to process images, videos, and voice files. Moreover, we discuss Polder based on the application development experience using Polder.

Hidden Markov models (HMMs) have received considerable attention in various communities (e.g, speech recognition, neurology and bioinformatic) since many applications that use HMM have emerged. The goal of this work is to identify efficiently and correctly the model in a given dataset that yields the state sequence with the highest likelihood with respect to the query sequence. We propose SPIRAL, a fast search method for HMM datasets. To reduce the search cost, SPIRAL efficiently prunes a significant number of search candidates by applying successive approximations when estimating likelihood. We perform several experiments to verify the effectiveness of SPIRAL. The results show that SPIRAL is more than 500 times faster than the naive method.

The goal of this paper is to monitor numerical streams, and to find subsequences that are similar to a given query sequence, under the DTW (dynamic time warping) distance. Applications include word spotting, sensor pattern matching, and monitoring of bio-medical signals (e.g., EKG, ECG), and monitoring of environmental (seismic and volcanic) signals. DTW is a very popular distance measure, permitting accelerations and decelerations, and it has been studied for finite, stored sequence sets. However, in many applications such as network analysis and sensor monitoring, massive amounts of data arrive continuously and it is infeasible to save all the historical data. We propose SPRING, a novel algorithm that can solve the problem. We provide a theoretical analysis and prove that SPRING does not sacrifice accuracy, while it requires constant space and time per time-tick. These are dramatic improvements over the naive method. Our experiments on real and realistic data illustrate that SPRING does indeed detect the qualifying subsequences correctly and that it can offer dramatic improvements in speed over the naive implementation.

Digital watermarking technology would be very useful as part of a related service introduction system (RSIS); which links physical objects in the real world, such as printed photographs, to those in the cyber world. In this paper, we focus on a camera-equipped mobile phone as an RSIS terminal, and propose a fast watermark detection scheme for the captured images. The proposed scheme consists of two processes; to correct geometric distortion of the captured image, and to detect watermark information from the corrected image. For our scheme, we also propose a fast quadrangle detection algorithm and a robust watermarking algorithm. Moreover, we introduce a quantitative evaluation method for determining the reliability of watermark detection, which is essential for RSIS services. Finally, we show that the proposed scheme enables users to detect embedded information far less than one second, even when implemented as a Java application on a mobile phone with limited resources, and our experiments confirm the efficiency of our scheme.

Range labeling and structural joins are well-studied techniques for efficiently processing XPath queries. However, when XPath queries become long, many times of structural joins are required. To solve this problem, we developed a method to reduce the number of joins and nodes read from the disk using strong DataGuides. Our method can process single paths without any joins and twig patterns with joins amongst branching nodes and leaves in queries. Experimental results verified that our approach outperforms the best optimization technique for structural joins by factors of up to several hundreds of times.

We developed a system that enables a camera-equipped cellular phone to read digital watermarks embedded in various media in real time, and that presents to the user a link to a Web page, video, or music associated with that watermark information. A picture captured by a camera is the result of applying a projective transformation combining rotation, scaling, and tilting to the original picture, The picture must be subjected to an inverse projective transformation prior to reading the watermark in order to return it to the same geometric form as the original picture. This inverse transformation requires transformation parameters, and the corners of the picture outline can be used as feature points for determining these parameters. In this paper, we propose a Side Trace Algorithm (STA) that reduces the processing time required to find corners of the picture less than 1/100 that when using the Hough transform and the conventional pattern matching, and present results of its implementation.

Digital watermarking technology would be very useful as part of a related service introduction system (RSIS); this system provides related information to content, and the function of watermark in RSIS is analogous to that of barcode, i.e., watermark binds content ID to analog content such as an image on printed material.In this paper, we focus on a camera-equipped cellular phone used as a terminal for RSIS, and propose a fast watermark detection scheme from a captured image. The proposed scheme consists of two processes, one is to correct geometric distortion of the captured image, and the other is to detect watermark information from the rectified image. We also propose a new watermarking algorithm which is robust against small geometric distortion and suitable for the proposed scheme. Moreover, we introduce a quantitative evaluation method for indicating detection reliability, which is indispensable for RSIS service.Finally, we show that the proposed scheme enables users to detect embedded information in approximately one second, even when implemented as a Java application on a cell phone with limited resources, and report experiments that confirm the proposed scheme's efficiency.

A music retrieval system that accepts hummed tunes as queries is described in this paper. This system uses similarity retrieval because a hummed tune may contain errors. The retrieval result is a list of song names ranked according to the closeness of the match. Our ultimate goal is that the correct song should be first on the list. This means that eventually our system's similarity retrieval should allow for only one correct answer.

No abstract available.