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.
- input:
- 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.
