Similarity search for multidimensional data sequences

Abstract

Time-series data, which are a series of one-dimensional real numbers, have been studied in various database applications such as data mining and data warehousing. In this thesis, we first extend the traditional similarity search methods on one-dimensional time-series data to support a multidimensional data sequence (MDS), such as digital signals, audio, and video streams. We investigate the similarity search methods for generalized multidimensional sequences from a large database. To prune irrelevant sequences in a database with respect to a given query, we introduce correct and efficient similarity functions. Both data sequences and query sequences are partitioned into subsequences, and each of them is represented by a minimum bounding rectangle (MBR). The query processing is based upon these MBRs, instead of scanning data elements of entire sequences. The method is designed (1) to select candidate sequences in a database, and (2) to find the subsequences of a selected sequence, each of which falls under the given threshold. The latter is of special importance in the case of retrieving subsequences from large and complex sequences. By using it, we do not need to browse the whole of the selected sequence, but just browse the sub-streams to find a part we want. Next, we investigate the similarity search methods for the specialized video domain using the concept of an MDS. A video clip, a sequence of video frames describing a particular event, is represented by an MDS which is partitioned into video segments considering temporal relationship among frames, and then similar segments of the clip are grouped into video clusters. We present the effective video segmentation and clustering algorithm that guarantees the clustering quality to such an extent that satisfies predefined conditions. Based on video segments and clusters generated by the algorithm, we define various similarity functions and present the effective similarity search methods to find relevant vi...