Patent ID: 7072891

Claim:
An apparatus for performing similarity searches using hyper-rectangle based multidimensional data segmentation, comprising: a multidimensional data sequence S i comprising one or more multidimensional data embodied in a computer readable storage medium, wherein said computer readable storage medium comprises: data segmentation means for segmenting a multidimensional data sequence S i comprising the one or more multidimensional data; and means for determining similarity between an inputted query data and the multidimensional data sequence S i ; wherein the data segmentation means comprises: threshold calculation means for inputting the multidimensional data sequence S i and a minimum number of points per segment minPts, and calculating a bounding threshold value for a volume and a bounding threshold value for an edge using a unit hyper-cube occupied by a single point in an n-dimensional unit space, if points are uniformly distributed in a hyper-rectangle which is a minimum bounding rectangle containing all points in the multidimensional data 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 multidimensional data sequence S i ; geometric condition determination means for determining whether at least one next point of the multidimensional data sequence S i satisfies a geometric condition using the bounding threshold value for the volume and the bounding threshold value for the edge; segment merging means for merging the at least one next point of the multidimensional data sequence S i into the current segment if the 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 at least one next point of the multidimensional data sequence S i , if the geometric condition is not satisfied and a number of points contained in the current segment exceeds the minimum number of points per segment minPts.