×

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
First Claim
Patent Images

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 Dmbr 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 Dnorm 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 Dnorm from each sequence obtained using the distance Dnorm.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×