Apparatus and method for similarity searches using hyper-rectangle based multidimensional data segmentation

• US 6,778,981 B2
• Filed: 03/22/2002
• Issued: 08/17/2004
• Est. Priority Date: 10/17/2001
• Status: Expired due to Fees

• Current Assignee: Korea Advanced Institute of Science and Technology
• Original Assignee: Korea Advanced Institute of Science and Technology
• Inventors: Chung, Chin-Wan, Kim, Deok-Hwan, Lee, Seok-Lyong, Chun, Seok-Ju
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): Wu, Yicun
• Application Number:
  US10/106,668
• Publication Number:
  US 20030097356A1
• Time in Patent Office: 879 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/8, 707/9, 707/10, 707/100, 707/101, 707/107, 707/103, 707/104.1, 702/27
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Disclosed herein is an apparatus and method for similarity searches using hyper-rectangle based multidimensional data segmentation. The similarity search apparatus has MBR generation means, first sequence pruning means, second sequence pruning means, and subsequence finding means. The MBR generation means segments a multidimensional data sequence to be partitioned into subsequences, and represents each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database. The first sequence pruning means prunes irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space. The second sequence pruning means prunes irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned in a multidimensional Euclidean space. The subsequence finding means detects subsequences similar to the given query sequence by obtaining sets of points contained in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm.

Claims

1. An apparatus for hyper-rectangle based multidimensional data similarity searches, the multidimensional data being representable by a multidimensional data sequence, comprising:

MBR generation means for segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

first sequence pruning means for pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

second sequence pruning means for pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned by the first sequence pruning means in a multidimensional Euclidean space; and

subsequence finding means for finding subsequences similar to the given query sequence by obtaining sets of points in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm.

2. The similarity search apparatus according to claim 1, wherein the distance D_mbr is the minimum distance between two hyper-rectangles.

3. The similarity search apparatus according to claim 1, wherein the distance D_norm is determined using:

(a) the number of points contained in each MBR;

(b) distance D_mbr between the query MBR and a target MBR in the data sequence; and

(c) distance D_mbr between the query MBR and an MBR adjacent to the target MBR in the data sequence.

4. An apparatus for hyper-rectangle based multidimensional data similarity searches, comprising:

MBR generation means for segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

first sequence pruning means for pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

second sequence pruning means for pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned by the first sequence pruning means in a multidimensional Euclidean space; and

subsequence finding means for finding subsequences similar to the given query sequence by obtaining sets of points in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm;

wherein the MBR generation means includes;

threshold calculation means for inputting a multidimensional sequence S_i and the minimum number of points per segment minPts, and calculating bounding threshold values for a volume and an edge using a unit hyper-cube occupied by a single point in n-dimensional unit space, if points are uniformly distributed in a hyper-rectangle which is a minimum bounding rectangle containing all points in the sequence S_i,

segment generation means for initializing a segment set and an outlier set to empty sets and generating a current segment using a first point of the sequence S_i,

geometric condition determination means for determining whether a next point of the sequence S_i satisfies a geometric condition using the bounding threshold values for the volume and the edge,

segment merging means for merging the next point of the sequence S_i into the current segment if geometric condition is satisfied, and

segment updating means for including the current segment in the segment set and re-generating a new current segment using the next point of the sequence S_i, if the geometric condition is not satisfied and the number of points contained in the current segment exceeds the minimum number of points per segment minPts.

5. The similarity search apparatus according to claim 4, wherein the geometric condition determination means determines that the geometric condition is satisfied if the following Equation [1] is satisfied:

6. An apparatus for hyper-rectangle based multidimensional data similarity searches, comprising:

MBR generation means for segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

first sequence pruning means for pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

second sequence pruning means for pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned by the first sequence pruning means in a multidimensional Euclidean space; and

subsequence finding means for finding subsequences similar to the given query sequence by obtaining sets of points in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm;

wherein the MBR generation means includes;

threshold calculation means for inputting a multidimensional sequence S_i and the minimum number of points per segment minPts, and calculating bounding threshold values for a volume and a semantic factor using a unit hyper-cube occupied by a single point in n-dimensional unit space, if points are uniformly distributed in a hyper-rectangle which is a minimum bounding rectangle containing all points in the sequence S_i,

segment generation means for initializing a segment set and an outlier set to empty sets and generating a current segment using a first point of the sequence S_i,

geometric and semantic condition determination means for determining whether a next point of the sequence S_i satisfies geometric and semantic conditions using the bounding threshold values for the volume and the semantic factor,

segment merging means for merging the next point of the sequence S_i into the current segment if the geometric and semantic conditions are satisfied, and

segment updating means for including the current segment in the segment set and re-generating a new current segment using the next point of the sequence S_i, if the geometric and semantic conditions are not satisfied and the number of points contained in the current segment exceeds the minimum number of points per segment minPts.

7. The similarity search apparatus according to claim 6, wherein the geometric and semantic condition determination means determines that the geometric and semantic conditions are satisfied if the following Equation [2] is satisfied:

8. An apparatus for hyper-rectangle based multidimensional data similarity searches, comprising:

MBR generation means for segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

first sequence pruning means for pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

second sequence pruning means for pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned by the first sequence pruning means in a multidimensional Euclidean space; and

subsequence finding means for finding subsequences similar to the given query sequence by obtaining sets of points in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm;

wherein the MBR generation means includes;

threshold calculation means for inputting a multidimensional sequence S_i and the minimum number of points per segment minPts, and calculating bounding threshold values for a volume, an edge and a semantic factor using a unit hyper-cube occupied by a single point in n-dimensional unit space, if points are uniformly distributed in a hyper-rectangle which is a minimum bounding rectangle containing all points in the sequence S_i,

segment generation means for initializing a segment set and an outlier set to empty sets and generating a current segment using a first point of the sequence S_i,

geometric and semantic condition determination means for determining whether a next point of the sequence S_i satisfies geometric and semantic conditions using the bounding threshold values for the volume, the edge and the semantic factor,

segment merging means for merging the next point of the sequence S_i into the current segment if the geometric and semantic conditions are satisfied, and

segment updating means for including the current segment in the segment set and re-generating a new current segment using the next point of the sequence S_i, if the geometric and semantic conditions are not satisfied and the number of points contained in the current segment exceeds the minimum number of points per segment minPts.

9. The similarity search apparatus according to claim 8, wherein the geometric and semantic condition determination means determines that the geometric and semantic conditions are satisfied if the following Equation [3] is satisfied:

10. A method for a hyper-rectangle based multidimensional data similarity searches, the multidimensional data being representable by a multidimensional data sequence, comprising the steps of:

segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned in a multidimensional Euclidean space; and

finding subsequences similar to the given query sequence by obtaining sets of points contained in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm.

11. The similarity search method according to claim 10, wherein the distance D_mbr is the minimum distance between two hyper-rectangles.

12. The similarity search method according to claim 10, wherein the distance D_norm is determined using:

(a) the number of points contained in each MBR;

(b) distance D_mbr between the query MBR and a target MBR in the data sequence; and

(c) distance D_mbr between the query MBR and an MBR adjacent to the target MBR in the data sequence.

13. A method for a hyper-rectangle based multidimensional data similarity searches, comprising the steps of:

segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned in a multidimensional Euclidean space; and

finding subsequences similar to the given query sequence by obtaining sets of points contained in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm;

wherein the MBR generation step includes the steps of;

inputting a multidimensional sequence S_i and the minimum number of points per segment minPts, and calculating bounding threshold values for a volume and an edge using a unit hyper-cube occupied by a single point in n-dimensional unit space, if points are uniformly distributed in a hyper-rectangle which is a minimum bounding rectangle containing all points in the sequence S_i,

initializing a segment set and an outlier set to empty sets and generating a current segment using a first point of the sequence S_i,

determining whether a next point of the sequence S_i satisfies a geometric condition using the bounding threshold values for the volume and the edge,

merging the next point of the sequence S_i into the current segment if the geometric condition is satisfied, and

including the current segment in the segment set and updating the segment set by re-generating a new current segment using the next point of the sequence S_i, if the geometric condition is not satisfied and the number of points contained in the current segment exceeds the minimum number of points per segment minPts.

14. The similarity search method according to claim 13, wherein at the geometric condition determination step, it is determined that the geometric condition is satisfied if the following Equation [4] is satisfied:

15. A method for a hyper-rectangle based multidimensional data similarity searches, comprising the steps of:

segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned in a multidimensional Euclidean space; and

finding subsequences similar to the given query sequence by obtaining sets of points contained in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm;

wherein the MBR generation step includes the steps of;

inputting a multidimensional sequence S_i and the minimum number of points per segment minPts and calculating bounding threshold values for a volume and a semantic factor using a unit hyper-cube occupied by a single point in n-dimensional unit space, if points are uniformly distributed in a hyper-rectangle which is a minimum bounding rectangle containing all points in the sequence S_i,

initializing a segment set and an outlier set to empty sets and generating a current segment using a first point of the sequence S_i,

determining whether a next point of the sequence S_i satisfies geometric and semantic conditions using the bounding threshold values for the volume and the semantic factor,

merging the next point of the sequence S_i into the current segment if the geometric and semantic conditions are satisfied, and

including the current segment in the segment set and updating the segment set by re-generating a new current segment using the next point of the sequence S_i, if the geometric and semantic conditions are not satisfied and the number of points contained in the current segment exceeds the minimum number of points per segment minPts.

16. The similarity search method according to claim 15, wherein at the geometric and semantic condition determination step, it is determined that the geometric and semantic conditions are satisfied if the following Equation [5] is satisfied:

17. A method for a hyper-rectangle based multidimensional data similarity searches, comprising the steps of:

segmenting a multidimensional data sequence to be partitioned into subsequences, and representing each subsequence by each Minimum Bounding Rectangle (MBR), such that sets of MBRs are generated from the multidimensional data sequence, and the MBR sets are stored in a database;

pruning irrelevant data sequences using a distance D_mbr between MBRs extracted from an inputted query sequence and the MBR sets stored in the database in a multidimensional Euclidean space;

pruning irrelevant data sequences using a normalized distance D_norm between MBRs extracted from the query sequence and the MBR sets of data sequences remaining after the data sequences are pruned in a multidimensional Euclidean space; and

finding subsequences similar to the given query sequence by obtaining sets of points contained in MBRs involved in a calculation of the distance D_norm from each sequence obtained using the distance D_norm;

wherein the MBR generation step includes the steps of;

inputting a multidimensional sequence S_i and the minimum number of points per segment minPts, and calculating bounding threshold values for a volume, an edge and a semantic factor using a unit hyper-cube occupied by a single point in n-dimensional unit space, if points are uniformly distributed in a hyper-rectangle which is a minimum bounding rectangle containing all points in the sequence S_i,

initializing a segment set and an outlier set to empty sets and generating a current segment using a first point of the sequence S_i,

determining whether a next point of the sequence S_i satisfies geometric and semantic conditions using the bounding threshold values for the volume, the edge and the semantic factor,

merging the next point of the sequence S_i into the current segment if the geometric and semantic conditions are satisfied, and

including the current segment in the segment set and updating the segment set by re-generating a new current segment using the next point of the sequence S_i, if the geometric and semantic conditions are not satisfied and the number of points contained in the current segment exceeds the minimum number of points per segment minPts.

18. The similarity search method according to claim 17, wherein at the geometric and semantic condition determination step, it is determined that the geometric and semantic conditions are satisfied if the following Equation [6] is satisfied: