Fast query search in large dimension database

• US 5,848,404 A
• Filed: 03/24/1997
• Issued: 12/08/1998
• Est. Priority Date: 03/24/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hafner, James Lee, Megiddo, Nimrod, Upfal, Eliezer
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/823,396
• Time in Patent Office: 624 Days
• Field of Search: 707/3, 707/100, 707/101, 707/5, 707/6
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer-implemented database search method includes arranging data points in a tree structure, with upper nodes being labeled by respective randomly selected representative data point and with the distance between each data point which is related to a first node and the label of the first node being less than the distance between the data point and the label of nodes in other branches. When a query is received, the distance between the query and the label of each node in the upper-most level is determined, and the nodes arranged in sequence, shortest distance first. Then, the process is repeated for the first "f" nodes in the sequence, and so on, until a sequence of leaves (i.e., data points having no dependent nodes or leaves) is obtained. The first "k" leaves are returned as the "k" closest database matches to the query. Alternatively, geometric information pertaining to the data points is recorded when the database is populated, and then, for query execution, nodes of data are ranked according to the geometric information as it relates to the query, with the node rankings terminated when a high bound for the geometric relationship between the query and a node is reached.

Claims

1. A computer including a data storage device including a computer usable medium having computer usable code means for identifying data points that are similar to a query, the data points being stored in a database accessible by the computer, the computer usable code means having:

computer readable code means for arranging the database in a tree structure having at least an internal node level including internal nodes, a leaf-parent node level including leaf-parent nodes, and a leaf level including leaves, each internal node and leaf-parent node representing clusters of data points, each cluster being defined by (1) a respective randomly selected representative data point and (2) respective dependent data points, the distance between each representative data point in a level and its dependent data points being less than the distance between the dependent data point and the respective representative data point of any other cluster in the level;

computer readable code means for receiving a query Q and in response determining respective query distances between the query Q and at least some of the representative data points;

computer readable code means for arranging the internal nodes of the respective at least some of the representative data points in a sequence from smallest query distance to greatest query distance; and

computer readable code means for returning a subsequence having a predetermined number of internal nodes, starting with the first node in the sequence.

2. The computer of claim 1, further comprising:

computer readable code means for receiving the subsequence of internal nodes and, for each internal node in the subsequence of internal nodes, determining respective query distances between the query Q and each representative data point in each leaf-parent node of the internal node;

computer readable code means for listing the leaf-parent nodes of each internal node in the subsequence of internal nodes in a sequence from smallest query distance to greatest query distance; and

computer readable code means for returning a subsequence of leaf-parent nodes having a predetermined number of leaf-parent nodes.

3. The computer of claim 2, further comprising:

computer readable code means for receiving the subsequence of leaf-parent nodes and, for each leaf in the subsequence of leaf-parent nodes, determining respective query distances between the query Q and each leaf;

computer readable code means for arranging the leaves of each leaf-parent node in the subsequence of leaf-parent nodes in a leaf sequence from smallest query distance to greatest query distance; and

computer readable code means for returning the first k leaves in the leaf sequence.

4. The computer of claim 3, further comprising computer readable code means for adding a data point to the database by adding a new leaf to the tree, the new leaf having, as a label, the data point, the new leaf being added to a leaf-parent node having a representative data point closer to the new leaf than the representative data points of the other leaf nodes.

5. The computer of claim 4, further comprising means for removing a data point in the database by deleting a leaf from the tree.

6. The computer of claim 3, further comprising computer readable code means for adding a data point to the database by adding a new leaf to the tree, the new leaf having, as a label, the data point, the new leaf being added to an auxiliary leaf-parent node, the auxiliary leaf-parent node being traversed for each query.

7. The computer of claim 5, further comprising means for removing a data point from the database by deleting a leaf from the tree.

8. A computer-implemented method for arranging data points in a database, comprising:

defining a first level of nodes including internal nodes, each internal node being labeled by a representative data point, the representative data points being randomly selected;

defining a second level of nodes including leaf-parent nodes, each leaf-parent node depending from an internal node, each leaf-parent node being labeled by a representative data point, each leaf-parent node including at least one leaf labeled by a data point, wherein

the distance between a leaf and the label of its leaf-parent node is less than the distance between the leaf and the label of any other leaf-parent node.

9. The computer-implemented method of claim 8, further comprising:

receiving a query Q and in response determining respective query distances between the query Q and each representative data point in each internal node;

arranging the internal nodes in a sequence from smallest query distance to greatest query distance; and

returning a subsequence having a predetermined number of internal nodes, starting with the first node in the sequence.

10. The computer-implemented method of claim 9, further comprising:

receiving the subsequence of internal nodes and, for each internal node in the subsequence of internal nodes, determining respective query distances between the query Q and each representative data point in each leaf-parent node;

arranging the leaf-parent nodes of each internal node in the subsequence of internal nodes in a sequence from smallest query distance to greatest query distance; and

returning a subsequence of leaf-parent nodes having a predetermined number of leaf-parent nodes.

11. The computer-implemented method of claim 10, further comprising:

receiving the subsequence of leaf-parent nodes and, for each leaf in the subsequence of leaf-parent nodes, determining respective query distances between the query Q and each leaf;

arranging the leaves of each leaf-parent node in the subsequence of leaf-parent nodes in a leaf sequence from smallest query distance to greatest query distance; and

returning the first k leaves in the leaf sequence.

12. The computer-implemented method of claim 11, further comprising adding a data point to the database by adding a new leaf to the tree, the new leaf having, as a label, the data point, the new leaf being added to a leaf-parent node having a representative data point closer to the new leaf than the representative data points of the other leaf nodes.

13. The computer-implemented method of claim 12, further comprising removing a data point from the database by deleting a leaf from the tree.

14. The computer-implemented method of claim 11, further comprising adding a data point to the database by adding a new leaf to the tree, the new leaf having, as a label, the data point, the new leaf being added to an auxiliary leaf-parent node, the auxiliary leaf-parent node being traversed for each query.

15. The computer-implemented method of claim 14, further comprising removing a data point from the database by deleting a leaf from the tree.

16. The computer-implemented method of claim 14, undertaken in combination with a digital processing apparatus.

17. A computer program device comprising:

a computer program storage device readable by a digital processing apparatus; and

a program means on the program storage device and including instructions for causing the digital processing apparatus to return "k" close matches in a database to a query Q, the database being arranged in a tree having nodes, each node being labeled by a respective representative data point, by;

receiving a query Q and in response determining respective query distances between the query Q and each representative data point in a predetermined number of test nodes;

arranging the test nodes in a sequence from smallest query distance to greatest query distance; and

returning a subsequence having a predetermined number of test nodes, starting with the first test node in the sequence.

18. The computer program device of claim 17, wherein the tree has at least an internal node level including internal nodes, a leaf-parent node level including leaf-parent nodes, and a leaf level including leaves, each internal node and leaf-parent node representing clusters of data points, each cluster being defined by (1) a respective randomly selected representative data point and (2) respective dependent data points, the test nodes being internal nodes and the subsequence being a subsequence of internal nodes, the instructions further causing the computer to:

receive the subsequence of internal nodes and, for each internal node in the subsequence of internal nodes, determine respective query distances between the query Q and each representative data point in each leaf-parent node;

arrange the leaf-parent nodes of each internal node in the subsequence of internal nodes in a sequence from smallest query distance to greatest query distance; and

return a subsequence of leaf-parent nodes having a predetermined number of leaf-parent nodes.

19. The computer program device of claim 18, wherein the instructions further cause the computer to:

receive the subsequence of leaf-parent nodes and, for each leaf in the subsequence of leaf-parent nodes, determine respective query distances between the query Q and each leaf;

arrange the leaves of each leaf-parent node in the subsequence of leaf-parent nodes in a leaf sequence from smallest query distance to greatest query distance; and

return the first k leaves in the leaf sequence.

20. The computer program device of claim 19, wherein the instructions further cause the computer to:

add a data point to the database by adding a new leaf to the tree, the new leaf having, as a label, the data point, the new leaf being added to a leaf-parent node having a representative data point closer to the new leaf than the representative data points of the other leaf nodes.

21. The computer program device of claim 19, wherein the instructions further cause the computer to:

add a data point to the database by adding a new leaf to the tree, the new leaf having, as a label, the data point, the new leaf being added to an auxiliary leaf-parent node, the auxiliary leaf-parent node being traversed for each query.

22. The computer program device of claim 20 or 21 wherein the instructions further cause the computer to remove a data point from the database by deleting a leaf from the tree.

23. The computer program device of claim 18, in combination with a digital processing apparatus.

24. A computer including a data storage device including a computer usable medium having computer usable code means for identifying data points that are similar to a query, the data points being stored in a database accessible by the computer, the computer usable code means having:

computer readable code means for arranging the database in a tree structure having data nodes, each node containing clusters of data points, each cluster being defined by (1) a respective randomly selected representative data point and (2) respective dependent data points;

computer readable code means for recording geometric information for each node;

computer readable code means for receiving a query Q and in response listing the nodes in a sequence of increasing order of lower bounds, the lower bounds being determined based on the geometric information; and

computer readable code means for returning the sequence of the nodes for searching thereof.

25. The computer of claim 24, further comprising:

computer readable code means for listing in the sequence of nodes only nodes having lower bounds less than a current upper bound between the query Q and a representative data point, the current upper bound being the greatest lower bound of a representative data point in the sequence.

26. The computer of claim 25, further comprising:

computer readable code means for determining a distance between a first representative data point and a second representative data point by determining, for the first representative data point, a polyhedron cell, and determining a first maximum distance that a hyperplane containing the first and second representative data points can be moved, in a direction parallel to a line connecting the first and second representative data points while intersecting the polyhedron cell.

27. The computer of claim 26, further comprising:

computer readable code means for determining an upper bound between the query Q and a representative data point by determining a maximum distance that a hyperplane containing the query Q and the representative data point can be moved in a predetermined direction without intersecting the polyhedron cell.

28. The computer of claim 25, further comprising:

computer readable code means for determining a distance between a first representative data point and a second representative data point by determining a first maximum distance that a hyperplane containing the first and second representative data points can be moved in a direction parallel to a line connecting the first and second representative data points while intersecting at least one predetermined data point.

29. The computer of claim 28, further comprising:

computer readable code means for determining an upper bound between the query Q and a representative data point by determining a maximum distance that a hyperplane containing the query Q and the representative data point can be moved in a predetermined direction without intersecting at least one predetermined data point.