Transformation-based method for indexing high-dimensional data for nearest neighbour queries

• US 20020147703A1
• Filed: 04/05/2001
• Published: 10/10/2002
• Est. Priority Date: 04/05/2001
• Status: Active Grant

• Current Assignee: Thoth Technology Incorporated
• Original Assignee: Thoth Technology Incorporated
• Inventors: Yu, Cui, Ooi, Beng-Chin, Tan, Kian-Lee
• Granted Patent: US 6,834,278 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

We disclose a transformation-based method for indexing high-dimensional data to support similarity search. The method, iDistance, partitions the data into clusters either based on some clustering strategies or simple data space partitioning strategies. The data in each cluster can be described based on their similarity with respect to a reference point, and hence they can be transformed into a single dimensional space based on such relative similarity. This allows us to index the data points using a B⁺-tree structure and perform similarity search using range search strategy. As such, the method is well suited for integration into existing DBMSs. We also study two data partitioning strategies, and several methods on selection of reference points. We conducted extensive experiments to evaluate iDistance, and our results demonstrate its effectiveness.

Claims

1. A method for indexing in a database of stored objects, the method comprising the following steps:

applying a clustering algorithm to organize high-dimensional points into partitions;

selecting a reference point for each partition;

applying a transformation function to map a high-dimensional point to a one-dimensional space;

indexing the transformed point using a single dimensional index structure.

2. A method for indexing as defined in claim 1 further comprising the step of conducting a KNN search on the indexed set of transformed points to retrieve a set of points which represent a superset of objects including the desired objects (i.e., nearest with respect to a distance metric to the query object) and false drops;

3. A method for indexing as defined in claim 2 further comprising the step of pruning away the false drops;

4. A method for indexing as defined in claim 1 wherein the step for partitioning high-dimensional data points is performed either via equi-space partitioning or cluster-based partitioning;

5. A method for indexing as defined in claim 4 wherein the equi-space partitioning splits a d-dimensional data space into 2d pyramids with the centroid of the unit cube space as their tip, and each hyperplane forming the base of each pyramid;

6. A method for indexing as defined in claim 4 wherein the cluster-based partitioning adopts a clustering strategy to obtain the partitions;

7. A method for indexing as defined in claim 1 wherein the step for selecting the reference points is performed via the following heuristics:

For equi-space partitioning, the reference point of a partition can be any point along the line formed by the centroid of a hyperplane and the centroid of the corresponding data space.

For cluster-based partitioning, either the centroid of the clusters or any points on the edge of the hyperplanes can be used as reference points.

8. A method for indexing as defined in claim 1 wherein the step for transforming includes mapping a high-dimensional points to its distance from the closest reference point.

9. A method for KNN search as defined in claim 2 wherein the method comprising the steps of

transforming the KNN search into a sequence of increasingly larger range queries;

each range query is evaluated on the single dimensional index structures storing the transformed points.

10. A method for KNN search as defined in claim 9 wherein approximate answers can be returned to the users as soon as they are found;

and the answers are progressively refined until all answers are obtained unless the users terminate prematurely.