Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-03-22
2004-08-17
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06778981
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to an apparatus and method for similarity searches using a hyper-rectangle based multidimensional data segmentation, and more particularly to an apparatus and method which can efficiently perform the segmentation with respect to data sets representable by multidimensional data sequences (MDS's), such as video streams, and can search for similarity using the segmentation.
2. Description of the Prior Art
For the past several years, time-series data have been thoroughly studied in database applications such as data mining and data warehousing. Time-series data are a series of real numbers, which represent values at time points. For example, the time-series data can be a sequence of real numbers such as the prices of stocks or commercial goods, weather patterns, sales indicators, biomedical measurements, and etc.
The examples of the time-series data are disclosed in detail in a thesis entitled “Similarity-Based queries for time series data” (May, 1997) by “D. Rafei, A. Medelzon” and published in “Proceedings of ACM SIGMOD Int'l Conference on Management of Data”. However, because such example values are basically one-dimensional data, most research still concentrates on indexes and searches for one-dimensional data sequences.
As the use of multimedia data has spread to many application domains, the efficient retrieval of multidimensional, voluminous and complex information, which are the intrinsic characteristics of multimedia data, is becoming increasingly important. The present invention, as described later, belongs to retrieval technology areas for data represented by sequences, such as time-series data and multimedia data, in accordance with this retrieval requirement.
In the prior art, various similarity search methods for time-series data have been proposed.
First, there is a whole sequence matching method. This method is described in detail in a thesis entitled “Efficient Similarity Search in Sequence Databases” by “R. Agrawal, C. Faloutsos, A. Swami” and published in “Proceedings of Foundations of Data Organizations and algorithms (FODO)”. The method is problematic in that two sequences to be compared must be of equal length. That is, the method maps the time sequences into the frequency domain, and uses the Discrete Fourier Transform (DFT) to solve the dimensionality curse problem. In this case, each sequence whose dimensionality is reduced by using the DFT is mapped into a lower-dimensional point in the frequency domain, and is indexed and stored using R*-Tree. However, this method is limited in that a database sequence and a query sequence must be of equal length, as described above.
Second, there is a fast subsequence matching method. This method is disclosed in detail in a thesis entitled “Fast Subsequence Matching in Time-Series Databases” by “C. Faloutsos, M. Ranganathan, Y. Manolopoulos” and published in “Proceedings of ACM SIGMOD Int'l Conference on Management of Data (May, 1994.)”. The basic idea of this method is that, using a sliding window with a size of w with respect to a data sequence, it represents w one-dimensional values included in each window by a single w-dimensional point, and transforms a one-dimensional data sequence into a lower-dimensional sequence using the DFT. The lower-dimensional data sequence is partitioned into subsequences. In this case, each subsequence is represented by a Minimum Bounding Rectangle (MBR) and is indexed and stored using “ST-index”. On the other hand, a query sequence is divided into one or more subsequences each with a size of w, each of which is represented by a w-dimensional point. The query processing is based on the MBRs of a data sequence stored in a database and each query point.
However, a point in the multidimensional sequence such as video sequences is semantically different from that of one-dimensional time-series data. In the multidimensional sequence, a point itself is a vector in the multidimensional space which has various feature values.
A query in a query process of the multidimensional sequence is given as a multidimensional sequence, and the query sequence is also divided into multiple subsequences. In one-dimensional sequence, each query subsequence is represented by a single point. However, in the multidimensional sequence, each subsequence cannot be represented by a single point, (because each point contained in each subsequence is multidimensional), such that this method cannot be used in the similarity search of the multidimensional sequence.
Further, this method performs clustering (or segmentation) based on a Marginal COST (MCOST) defined as the average number of disk accesses (DA) divided by the number of points in the MBR. That is, if a point is to be included in the cluster or MBR during the segmentation process, this algorithm considers the volume increment of the cluster due to the point included in the cluster as an important clustering factor in determining the MCOST. However, because the algorithm only considers the volume factor, it is insufficient to cover all of possible cases.
Third, there is a method using a set of safe linear transformations of a given sequence. This method is disclosed in detail in a thesis entitled “Similarity—Based queries for time series data (May, 1997)” by “D. Rafei, A. Mendelzon” and published in “Proceedings of ACM SIGMOD Int'l Conference on Management of Data”.
The set of safe linear transformations of the given sequence can be used as the basis of similarity queries for time-series data. Elements of this set formulate functions such as moving average, reversing and time warping. At this time, such transformation functions are extended to multiple transformations, where an index is searched for only once and a collection of transformations are simultaneously applied to the index, instead of searching for the index multiple times and each time applying a single transformation.
However, all of the above proposed methods handle the similarity search for one-dimensional time-series data, such that the methods cannot be applied to the multidimensional data sequence. Further, these methods are problematic in that they only focus on the problem of searching a database for candidate sequences whose similarities to a query sequence do not exceed a given threshold.
Meanwhile, a similarity search method for multidimensional data sequence, as proposed later in the present invention, uses a hyper-rectangle based segmentation, and technical fields related to the hyper-rectangle based segmentation are described as follows.
A clustering problem has been considerably studied in many database applications such as customer segmentation, sales analysis, pattern recognition and similarity search. The task of clustering data points is defined as follows: “Given a set of points in a multidimensional space, partition the points into clusters such that points within each cluster have similar characteristics while points in different clusters are dissimilar. At this time, a point that is considerably dissimilar to or inconsistent with the remainder of the data is referred to as an outlier.”
Conventional methods for clustering data points in a multidimensional space can include the following methods.
First, there is a method named “CLARANS” proposed in a thesis entitled “Efficient and effective clustering methods for spatial data mining” by “R. T. Ng and J. Han” and published in “Proceedings of Int'l Conference on Very Large Data Bases”. The CLARANS method is based on a randomized search method and achieves its efficiency by reducing the search space using two user-supplied input parameters.
Second, there is a method named “BIRCH” proposed in a thesis entitled “BIRCH: An efficient data clustering method for very large databases” by “T. Zhang, R. Ramakrishnan, and M. Livny” and published in “Proceedings of ACM SIGMOD Int'l Conference on Management of Data”. The “BIRCH” method is a multiphase clustering method for constructing a hierarchical data structure called
Chun Seok-Ju
Chung Chin-Wan
Kim Deok-Hwan
Lee Seok-Lyong
Bachman & LaPointe P.C.
Korea Advanced Institute of Science & Technology
Mizrahi Diane D.
Wu Yicun
LandOfFree
Apparatus and method for similarity searches using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for similarity searches using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for similarity searches using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306632