# 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:
- 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

### 2009

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

### 2007

- (Zezula et al., 2007) ⇒ Pavel Zezula, Giuseppe Amato, and Vlastislav Dohnal. (2007). “Similarity Search - The Metric Space Approach." Tutorial at ACM SAC 2007.

### 2006

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