Nearest Neighbor Query, Definition

Definition

Given a set P of n points in a d-dimensional space $\mathfrak{R}^{d}$ and a query point $q \in \mathfrak{R}^{d}$, a nearest neighbor (NN) query is to find the set of nearest points to the query point q. Formally, $NN\left (q\right ) = \left \{p\vert p \in P,\forall o \in P,(o\neq p),\vert qp\vert < \left \vert qo\right \vert \right \}$. In most cases, $\mathfrak{R}^{d}$ refers to a d-dimensional Euclidean space.

Main Text

Nearest neighbor search is one of the oldest problems in computer science. The NN algorithm was one of the earliest algorithms used to determine a solution to the traveling salesman problem (TSP). The NN query first appeared in Geographic Information Systems around 1990 and has now already become a frequently encountered query type in this field. Recently, several NNalgorithms have been proposed for NN queries based on spatial access methods (e.g., quad-trees, R-trees). For all these algorithms, depth-first search (DFS) and breadth-first search (BFS...