(1+ε)-approximate nearest neighbor search

Variant 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.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 https://dl.acm.org/doi/pdf/10.5555/313559.313768 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 k-d trees,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 https://dl.acm.org/doi/pdf/10.5555/314464.314652 978-0-89871-329-9 locality-sensitive hashing and brute-force search. References Category:Approximation algorithms Category:Classification algorithms Category:Search algorithms