Nearest Neighbor Search Task

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

AKA: Nearest Neighbor Task, Nearest Neighbor Search, Nearest Neighbour Search Task.
Context:
- input:
  - a Metric Space [math]M[/math] (with point space [math]P[/math] and distance function [math]d[/math]).
  - a Query Point [math]q \in P[/math]
  - a Positive Integer [math]k[/math].
- output: the [math]k[/math] points in [math]P[/math] closest to q.
- It can be:
  - a 1-Nearest Neighbor Search Task.
  - a k-Nearest Neighbor Search Task.
- It can be an Approximate Nearest Neighbor Search Task.
- It can be solved by a Nearest Neighbor Search Algorithm.
Example(s):
- Where is the nearest hospital?
- What are the four restaurants closest to my home?
See: Reverse Nearest Neighbor Search Task.

References

(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.