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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description (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 from a query point, where Шаблон:Mvar 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+Шаблон:Mvar)-approximate nearest neighbor search include kd-trees,[2] Locality Sensitive Hashing and brute force search.

References

Шаблон:Reflist


Шаблон:Algorithm-stub