(1+ε)-approximate nearest neighbor search explained

(1+)-approximate nearest neighbor search is a variant of the nearest neighbor search problem. A solution to the (1+)-approximate nearest neighbor search is a point or multiple points within distance (1+) from a query point, where is the distance between the query point and its true nearest neighbor.^[1]

Reasons to approximate nearest neighbor search include the space and time costs of exact solutions in high-dimensional spaces (see curse of dimensionality) and that in some domains, finding an approximate nearest neighbor is an acceptable solution.

Approaches for solving (1+)-approximate nearest neighbor search include kd-trees,^[2] Locality Sensitive Hashing and brute force search.

Notes and References

1. Arya. Sunil. Mount. David M.. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions . 271–280 . Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms . 978-0-89871-313-8 .
2. Arya. Sunil. Mount. David M.. Netanyahu. Nathan. Silverman. Ruth. Wu. Angela Y.. 1994. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions . Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms . 573–582 . 978-0-89871-329-9 .