EducationBot: Новая страница: «{{Английская Википедия/Панель перехода}} {{Short description|Special case of the nearest neighbor search problem}} '''(1+{{mvar|ε}})-approximate nearest neighbor search''' is a variant of the nearest neighbor search problem. A solution to the (1+{{mvar|ε}})-approximate nearest neighbor search is a point or multiple points within distance (1+{{mvar|ε}}) {{mvar|R}} from a query point, where {{mvar|R}} is the distance bet...»

2023-12-17T19:14:47Z

Новая страница: «{{Английская Википедия/Панель перехода}} {{Short description|Special case of the nearest neighbor search problem}} '''(1+{{mvar|ε}})-approximate nearest neighbor search''' is a variant of the nearest neighbor search problem. A solution to the (1+{{mvar|ε}})-approximate nearest neighbor search is a point or multiple points within distance (1+{{mvar|ε}}) {{mvar|R}} from a query point, where {{mvar|R}} is the distance bet...»

Новая страница

{{Английская Википедия/Панель перехода}}
{{Short description|Special case of the nearest neighbor search problem}}
'''(1+{{mvar|ε}})-approximate nearest neighbor search''' is a variant of the [[nearest neighbor search]] problem. A solution to the (1+{{mvar|ε}})-approximate nearest neighbor search is a point or multiple points within distance (1+{{mvar|ε}}) {{mvar|R}} from a query point, where {{mvar|R}} is the distance between the query point and its true nearest neighbor.<ref>{{Cite conference |last1=Arya|first1=Sunil|last2=Mount|first2=David M.|date=1993|title=Approximate Nearest Neighbor Queries in Fixed Dimensions |pages=271–280 |book-title=Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |isbn=978-0-89871-313-8 |url=https://dl.acm.org/doi/pdf/10.5555/313559.313768
}}</ref>

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+{{mvar|ε}})-approximate nearest neighbor search include [[kd-tree]]s,<ref>{{Cite conference |last1=Arya|first1=Sunil|last2=Mount|first2=David M.|last3=Netanyahu|first3=Nathan|last4=Silverman|first4=Ruth|last5=Wu|first5=Angela Y.|date=1994|title=An optimal algorithm for approximate nearest neighbor searching in fixed dimensions |book-title=Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms |pages=573–582 |url=https://dl.acm.org/doi/pdf/10.5555/314464.314652 |isbn=978-0-89871-329-9 }}</ref> [[Locality Sensitive Hashing]] and [[brute force search]].

==References==
{{reflist}}

{{DEFAULTSORT:(1 + epsilon)-approximate nearest neighbor search}}
[[Category:Approximation algorithms]]
[[Category:Classification algorithms]]
[[Category:Search algorithms]]

{{algorithm-stub}}
{{Навигационная таблица/Портал/Английская Википедия}}
[[Категория:Английская Википедия]]
[[Категория:Википедия]]
[[Категория:Статья из Википедии]]
[[Категория:Статья из Английской Википедии]]

Английская Википедия:(1+ε)-approximate nearest neighbor search - История изменений