(1+ε)-approximate nearest neighbor search

(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+ $ε$ ) $R$ from a query point, where $R$ 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.

References

^ Arya, Sunil; Mount, David M. (1993). "Approximate Nearest Neighbor Queries in Fixed Dimensions". Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 271–280. ISBN 978-0-89871-313-8.
^ 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. pp. 573–582. ISBN 978-0-89871-329-9.

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

[1] Arya, Sunil; Mount, David M. (1993). "Approximate Nearest Neighbor Queries in Fixed Dimensions". Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 271–280. ISBN 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. pp. 573–582. ISBN 978-0-89871-329-9.

[1]

[2]