Indexing system and method for nearest neighbor searches in high dimensional data spaces

A computer program product including a program of instructions having:

• computer readable code means for generating approximations including local polar coordinates of at least some data vectors p in at least one data set having a dimensionality of “d”, the local polar coordinates being independent of “d”;
• and
• computer readable code means for using the approximations to return “k” nearest neighbors to a query, wherein
• it is determined whether a minimum distance dmin between a query vector q and a candidate data vector is treater than a kth-largest distance in an initially null answer set, and if so, the candidate data vector is not returned among the “k” nearest neighbors.

A computer-implemented method for finding, in a data space, “k” closest data vectors p to a query vector q, comprising:

• rendering approximations of at least some of the data vectors p using local polar coordinates;
• filtering the approximations;
• and
• after filtering, returning the “k” closest data vectors p, wherein
• a kth-largest distance is set equal to a maximum distance associated with data vectors p in an answer set “knn”, actual data points represented by candidate vectors in a candidate set being scanned in increasing order of distance such that a candidate vector is retrieved and a distance between the candidate vector and the query vector q is compared to the kth-largest distance, and if the distance between the candidate vector and the query vector q is not less than kth-largest distance, a next candidate vector in the candidate set is retrieved, otherwise the candidate vector is inserted into the answer set “knn” and the kth-largest distance is recomputed.