METHOD AND APPARATUS FOR FACILITATING FINDING A NEAREST NEIGHBOR IN A DATABASE
A method and apparatus for facilitating finding a nearest neighbor in a database. Example embodiments include: accessing a database tree having a plurality of nodes; receiving information indicative of a query point and information indicative of a node in the database tree; determining, by use of a processor, a lower-bound estimate based on the node and the query point, wherein the lower-bound estimate corresponds to a distance from the query point to the node; determining, by use of the processor, a temporary result corresponding to a distance to a nearest neighbor based on at least one child node of the node, the query point, and the lower-bound estimate; pruning one or more of the plurality of nodes based on the lower-bound estimate and a pruning bound; and returning a result indicative of a nearest neighbor of the query point.
1 . A method comprising:
accessing a database tree having a plurality of nodes;
receiving information indicative of a query point and information indicative of a node in the database tree;
determining, by use of a processor, a lower-bound estimate based on the node and the query point, wherein the lower-bound estimate corresponds to a distance from the query point to the node;
determining, by use of the processor, a temporary result corresponding to a distance to a nearest neighbor based on at least one child node of the node, the query point, and the lower-bound estimate;
pruning one or more of the plurality of nodes based on the lower-bound estimate and a pruning bound; and
returning a result indicative of a nearest neighbor of the query point.
2 . The method of claim 1 including determining a distance from the query point to a leaf node.
3 . The method of claim 1 wherein the node is not a leaf node.
4 . The method of claim 1 including determining a distance from the query point to a plurality of bounding boxes corresponding to the node.
5 . The method of claim 4 wherein each of the plurality of bounding boxes corresponding to the node includes a hierarchical arrangement of sub-boxes.
6 . The method of claim 4 including determining a minimum distance from the query point to each of the plurality of bounding boxes corresponding to the node.
7 . The method of claim 4 including determining a minimum distance from the query point to each of a plurality of sub-boxes of each of the plurality of bounding boxes corresponding to the node.
8 . The method of claim 1 wherein the query point corresponds to a database query.
9 . A system comprising:
a processor;
a database query processor interface, in data communication with the processor, to receive a query point and information indicative of a node in a database tree; and
a database query processor, in data communication with the processor, to:
access a database tree having a plurality of nodes;
receive information indicative of a query point and information indicative of a node in the database tree;
determine, by use of the processor, a lower-bound estimate based on the node and the query point, wherein the lower-bound estimate corresponds to a distance from the query point to the node;
determine, by use of the processor, a temporary result corresponding to a distance to a nearest neighbor based on at least one child node of the node, the query point, and the lower-bound estimate;
prune one or more of the plurality of nodes based on the lower-bound estimate and a pruning bound; and
return a result indicative of a nearest neighbor of the query point.
10 . The system of claim 9 being further configured to determine a distance from the query point to a leaf node.
11 . The system of claim 9 wherein the node is not a leaf node.
12 . The system of claim 9 being further configured to determine a distance from the query point to a plurality of bounding boxes corresponding to the node.
13 . The system of claim 12 wherein each of the plurality of bounding boxes corresponding to the node includes a hierarchical arrangement of sub-boxes.
14 . The system of claim 12 being further configured to determine a minimum distance from the query point to each of the plurality of bounding boxes corresponding to the node.
15 . The system of claim 12 being further configured to determine a minimum distance from the query point to each of a plurality of sub-boxes of each of the plurality of bounding boxes corresponding to the node.
16 . The system of claim 9 wherein the query point corresponds to a database query.
17 . An article of manufacture comprising a non-transitory machine-readable storage medium having machine executable instructions embedded thereon, which when executed by a machine, cause the machine to:
access a database tree having a plurality of nodes;
receive information indicative of a query point and information indicative of a node in the database tree;
determine, by use of a processor, a lower-bound estimate based on the node and the query point, wherein the lower-bound estimate corresponds to a distance from the query point to the node;
determine, by use of the processor, a temporary result corresponding to a distance to a nearest neighbor based on at least one child node of the node, the query point, and the lower-bound estimate;
prune one or more of the plurality of nodes based on the lower-bound estimate and a pruning bound; and
return a result indicative of a nearest neighbor of the query point.
18 . The article of manufacture of claim 17 being further configured to determine a distance from the query point to a plurality of bounding boxes corresponding to the node.
19 . The article of manufacture of claim 18 wherein each of the plurality of bounding boxes corresponding to the node includes a hierarchical arrangement of sub-boxes.
20 . The article of manufacture of claim 18 being further configured to determine a minimum distance from the query point to each of the plurality of bounding boxes corresponding to the node.