Method for computing near neighbors of a query point in a database

Abstract

Abstract A method for determining k nearest-neighbors to a query point in a database in which an ordering is defined for a data set P of a database, the ordering being based on l one-dimensional codes C 1 , . . . , C 1 . A single relation R is created in which R has the attributes of index-id, point-id and value. An entry (j,i,C.sub.εj (p i )) is included in relation R for each data point p i ΕP, where index-id equals j, point-id equals i, and value equals C.sub.εj (p i ). A B-tree index is created based on a combination of the index-id attribute and the value attribute. A query point is received and a relation Q is created for the query point having the attributes of index-id and value. One tuple is generated in the relation Q for each j, j=1, . . . , l, where index-id equals j and value equals C.sub.εj (q). A distance d is selected. The index-id attribute for the relation R of each data point p i is compared to the index-id attribute for the relation Q of the query point. A candidate data point p i is selected when the comparison of the relation R of a data point p i to the index-id attribute for the relation Q of the query point is less than the distance d. Lower bounds are calculated for each cube of the plurality of cubes that represent a minimum distance between any point in a cube and the query point. Lastly, k candidate data points p i are selected as k nearest-neighbors to the query point.

Inventors

• 👤 Nimrod Megiddo
• 👤 Uri Shaft

Bibliographic Details