(1+ε)-approximate nearest neighbor search

ε-approximate nearest neighbor search is a special case of nearest neighbor search in which we are searching for points that are close to a query point. More formally, the goal is to report a point or multiple points within distance (1+ε) R from a query point, where R is the distance between the query point and its true nearest neighbor (NN).

One may want to solve NNS approximately because no efficient algorithms exist for exact NNS in high dimensional spaces (see curse of dimensionality) or because in their specific problem, finding an approximate NN is almost as good as finding the true NN.

Approaches for solving ε-approximate nearest neighbor search include kd-trees, Locality Sensitive Hashing and exhaustive search.