Patent US5848404A successfully refreshed from Google Patents.
US5848404A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast query search in large dimension database
Assignee: International Business Machines Corp
•
Filing: 1997-03-24
•
Granted: 1998-12-08
•
Expires: 2017-03-24
Abstract
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.
Inventors
- 👤 James Lee Hafner
- 👤 Nimrod Megiddo
- 👤 Eliezer Upfal
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 13:57
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
232 words
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.
Claim 2
Dependent Claim
232 words
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.
Claim 3
Dependent Claim
99 words
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.
Claim 4
Dependent Claim
84 words
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.
Claim 5
Dependent Claim
66 words
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.
Claim 6
Dependent Claim
23 words
The computer of claim 4, further comprising means for removing a data point in the database by deleting a leaf from the tree.
Claim 7
Dependent Claim
56 words
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.
Claim 8
Dependent Claim
23 words
The computer of claim 5, further comprising means for removing a data point from the database by deleting a leaf from the tree.
Claim 9
Dependent Claim
106 words
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.
Claim 10
Dependent Claim
106 words
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.
Claim 11
Dependent Claim
66 words
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.
Claim 12
Dependent Claim
81 words
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.
Claim 13
Dependent Claim
70 words
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.
Claim 14
Dependent Claim
62 words
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.
Claim 15
Dependent Claim
22 words
The computer-implemented method of claim 12, further comprising removing a data point from the database by deleting a leaf from the tree.
Claim 16
Dependent Claim
52 words
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.
Claim 17
Dependent Claim
22 words
The computer-implemented method of claim 14, further comprising removing a data point from the database by deleting a leaf from the tree.
Claim 18
Dependent Claim
14 words
The computer-implemented method of claim 14, undertaken in combination with a digital processing apparatus.
Claim 19
Dependent Claim
128 words
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.
Claim 20
Dependent Claim
128 words
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.
Claim 21
Dependent Claim
158 words
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.
Claim 22
Dependent Claim
77 words
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.
Claim 23
Dependent Claim
69 words
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.
Claim 24
Dependent Claim
59 words
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.
Claim 25
Dependent Claim
31 words
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.
Claim 26
Dependent Claim
14 words
The computer program device of claim 18, in combination with a digital processing apparatus.
Claim 27
Dependent Claim
146 words
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.
Claim 28
Dependent Claim
146 words
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.
Claim 29
Dependent Claim
55 words
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.
Claim 30
Dependent Claim
78 words
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.
Claim 31
Dependent Claim
54 words
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.
Claim 32
Dependent Claim
70 words
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.
Claim 33
Dependent Claim
57 words
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.
References Cited (Backward Citations)
US4135147A
Cited
US4667550A
Cited
US4799270A
Cited
US5276895A
Cited
US5404512A
Cited
US5485612A
Cited
US5289567A
Cited
US5329596A
Cited
US5350303A
Cited
US5331554A
Cited
US5497485A
Cited
US5701467A
Cited
US5521910A
Cited
US5710916A
Cited
US5664174A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-07 | 2002-06-08 | 2002-12-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-07 | 2006-06-08 | 2006-12-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-07 | 2010-06-08 | 2010-12-08 | $7700.00 | Window Closed / Lapsed |