Patent ID: 6148295
Filing Date: 2000-11-14
Classification: G06F,G06K,Y10S

Abstract:
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.sub.1, . . . , C.sub.l ;creating a single relation R having attributes index-id, point-id and value;including an entry (j,i,C.sub..epsilon.j (p.sub.i) in relation R for each data point p.sub.i .EPSILON.P, where index-id equals j, point-id equals i, and value equals C.sub..epsilon.j (p.sub.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..epsilon.j (q);selecting a distance d;comparing the index-id attribute for the relation R of each data point p.sub.i to the index-id attribute for the relation Q of the query point;selecting a candidate data point p.sub.i when the comparison of the relation R of a data point p.sub.i to the index-id attribute for the relation Q of the query point is less than the distance d; andselecting k candidate data points p.sub.i as k nearest-neighbors to the query point.