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.sub.1, . . . , C.sub.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..epsilon.j (p.sub.i)) is included 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). 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..epsilon.j (q). A distance d is selected. The index-id attribute for the relation R of each data point p.sub.i is compared to the index-id attribute for the relation Q of the query point. A candidate data point p.sub.i is selected 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. 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.sub.i are selected as k nearest-neighbors to the query point.