Nearest Neighbor Search Task

Jump to: navigation, search

A nearest neighbor search task is a similarity search task that requires finding points in a Nearest Neighbor Relation.



  • (Wikipedia, 2009) ⇒
    • Nearest neighbor search (NNS), also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q. In many cases, M is taken to be d-dimensional Euclidean space and distance is measured by Euclidean distance or Manhattan distance.
    • Donald Knuth in vol. 3 of The Art of Computer Programming (1973) called it the post-office problem, referring to an application of assigning a residence to the nearest post office.