(1+ε)-approximate nearest neighbor search
From HandWiki
Short description: Special case of the nearest neighbor search problem
(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". pp. 271–280. ISBN 978-0-89871-313-8. https://dl.acm.org/doi/pdf/10.5555/313559.313768.
- ↑ Arya, Sunil; Mount, David M.; Netanyahu, Nathan; Silverman, Ruth; Wu, Angela Y. (1994). "An optimal algorithm for approximate nearest neighbor searching in fixed dimensions". pp. 573–582. ISBN 978-0-89871-329-9. https://dl.acm.org/doi/pdf/10.5555/314464.314652.
 |  |
