Nearest Neighbor Search Task
- AKA: Nearest Neighbor Task, Nearest Neighbor Search, Nearest Neighbour Search Task.
- output: the [math]k[/math] points in [math]P[/math] closest to q.
- It can be:
- It can be an Approximate Nearest Neighbor Search Task.
- It can be solved by a Nearest Neighbor Search Algorithm.
- Where is the nearest hospital?
- What are the four restaurants closest to my home?
- See: Reverse Nearest Neighbor Search Task.
- (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Nearest_neighbor_search
- 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.
- (Zezula et al., 2007) ⇒ Pavel Zezula, Giuseppe Amato, and Vlastislav Dohnal. (2007). “Similarity Search - The Metric Space Approach." Tutorial at ACM SAC 2007.
- (Zezula et al., 2006) ⇒ Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. (2006). “Similarity Search: The Metric Space Approach." Springer, Advances in Database Systems.