Back to results
US 7,072,891 B2Granted
Apparatus and method for hyper-rectangle based multidimensional data segmentation and clustering
AssigneeKorea Advanced Institute of Science and Technology
InventorsSeok-Lyong Lee, Seok-Ju Chun, Deok-Hwan Kim, Chin-Wan Chung
Life of this patent
Estimating the term…
Abstract
An apparatus and method for performing similarity searches using hyper-rectangle based multidimensional data segmentation partitions a data set representable by a multidimensional data sequence, such as a video stream, into segments in consideration of the temporal relationship between points, and groups similar segments in one sequence into the same cluster so as to efficiently search a database for a multidimensional data sequence similar to a given query sequence.
Claims16
An apparatus for performing similarity searches using hyper-rectangle based multidimensional data segmentation, comprising:
- a multidimensional data sequence Si 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 Si comprising the one or more multidimensional data;
- and
- means for determining similarity between an inputted query data and the multidimensional data sequence Si;
- wherein the data segmentation means comprises:
- threshold calculation means for inputting the multidimensional data sequence Si 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 Si;
- 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 Si;
- geometric condition determination means for determining whether at least one next point of the multidimensional data sequence Si 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 Si 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 Si, 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.
8 more elements
An apparatus for performing similarity searches using hyper-rectangle based multidimensional data segmentation, comprising:
- a multidimensional data sequence Si 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 the multidimensional data sequence Si comprising the one or more multidimensional data;
- and
- means for determining similarity between an inputted query data and the multidimensional data sequence Si;
- wherein the data segmentation means comprises:
- threshold calculation means for inputting the multidimensional data sequence Si and a minimum number of points per segment minPts, and calculating a bounding threshold value for a volume and a bounding threshold value for a semantic factor 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 Si;
- 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 Si;
- geometric and semantic condition determination means for determining whether at least one next point of the multidimensional data sequence Si satisfies a geometric condition and a semantic condition using the bounding threshold value for the volume and the bounding threshold value for the semantic factor;
- segment merging means for merging at least one next point of the multidimensional data sequence Si 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 Si, 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.
8 more elements
An apparatus for using hyper-rectangle based multidimensional data segmentation in performing similarity searches, comprising:
- a multidimensional data sequence Si 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 the multidimensional data sequence Si comprising the one or more multidimensional data;
- and
- means for determining similarity between an inputted query data and the multidimensional data sequence Si;
- wherein the data segmentation means comprises:
- threshold calculation means for inputting the multidimensional sequence data Si and a minimum number of points per segment minPts, and calculating a bounding threshold value for a volume, a bounding threshold value for an edge and a bounding threshold value for 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 multidimensional data sequence Si;
- 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 Si;
- geometric and semantic condition determination means for determining whether at least one next point of the multidimensional sequence Si satisfies a geometric condition and a semantic condition using the bounding threshold values for the volume, the edge and the semantic factor;
- segment merging means for merging the at least one next point of the multidimensional sequence Si into the current segment if the geometric condition and the semantic condition are 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 Si, if the geometric condition and the semantic condition are not satisfied and a number of points contained in the current segment exceeds the minimum number of points per segment minPts.
8 more elements
A comDuter-implemented method for using hyper-rectangle based multidimensional data segmentation in performing similarity searches, comprising the steps of:
- segmenting a multidimensional data sequence Si comprising one or more multidimensional data embodied in a computer readable storage medium;
- and
- determining similarity between an inputted query data and the multidimensional data sequence Si;
- wherein the step of segmenting the multidimensional data sequence Si comprises:
- inputting the multidimensional data sequence Si 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 Si;
- 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 Si;
- determining whether at least one next point of the multidimensional data sequence Si satisfies a geometric condition using the bounding threshold values for the volume and the edge;
- merging the at least one next point of the multidimensional data sequence Si 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 at least one next point of the multidimensional data sequence Si, 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.
7 more elements
A computer-implemented method for using hyper-rectangle based multidimensional data segmentation in performing similarity searches, comprising the steps of:
- segmenting a multidimensional data sequence Si comprising one or more multidimensional data embodied in a computer readable storage medium;
- and
- determining similarity between an inputted query data and the multidimensional data sequence Si;
- wherein the step of segmenting a multidimensional data sequence Si comprises:
- inputting the multidimensional data sequence Si and a minimum number of points per segment minPts and calculating a bounding threshold value for a volume and a bounding threshold value for 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 multidimensional data sequence Si;
- 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 Si;
- determining whether at least one next point of the multidimensional data sequence Si satisfies a geometric condition and a semantic condition using the bounding threshold values for the volume and the semantic factor;
- merging the at least one next point of the multidimensional data sequence Si into the current segment if the geometric condition and the semantic condition 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 at least one next point of the multidimensional data sequence Si, if the geometric and semantic conditions are not satisfied and a number of points contained in the current segment exceeds the minimum number of points per segment minPts.
7 more elements
A computer-implemented method for using hyper-rectangle based multidimensional data segmentation in performing similarity searches, comprising the steps of:
- segmenting a multidimensional data sequence Si comprising one or more multidimensional data embodied in a computer readable storage medium;
- and
- determining similarity between an inputted query data and the multidimensional data sequence Si;
- wherein the step of segmenting the multidimensional data sequence Si comprises:
- inputting the multidimensional data sequence Si and a minimum number of points per segment minPts, and calculating a bounding threshold value for a volume, a bounding threshold value for an edge and a bounding threshold value for a semantic factor 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 Si;
- 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 Si;
- determining whether at least one next point of the multidimensional data sequence Si satisfies a geometric condition and a semantic condition using the bounding threshold values for the volume, the edge and the semantic factor;
- merging the at least one next point of the multidimensional data sequence Si into the current segment if the geometric condition and the semantic condition 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 at least one next point of the multidimensional data sequence Si, if the geometric and semantic conditions are not satisfied and a number of points contained in the current segment exceeds the minimum number of points per segment minPts.
7 more elements
Dependencies are inferred from the claim text.