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

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.

What is claimed is: 
     
       1. A method for determining k nearest-neighbors to a query point in a database, the method comprising the steps of: defining an ordering for a data set P of a database, the ordering being based on l one-dimensional codes C 1 , . . . , C l  ;   creating a single relation R having attributes index-id, point-id and value;   including an entry (j,i,C.sub.εj (p i ) 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 );   creating a B-tree index based on a combination of the index-id attribute and the value attribute;   receiving a query point;   creating a relation Q for the query point having attributes index-id and value;   generating one tuple in the relation Q for each j, j=1, . . . , l, where index-id equals j and value equals C.sub.εj (q);   selecting a distance d;   comparing the index-id attribute for the relation R of each data point p i  to the index-id attribute for the relation Q of the query point;   selecting a candidate data point p i  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; and   selecting k candidate data points p i  as k nearest-neighbors to the query point.   
     
     
       2. The method according to claim 1, wherein the step of defining an ordering for a data set P of a database forms a plurality of cubes, the method further comprising the steps of: calculating lower bounds for each cube of the plurality of cubes, the lower bound representing a minimum distance between any point in a cube and the query point; and   terminating the step of comparing when no lower bound is less than a distance between the query point and any of the candidate data points.