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 ddimensional 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 postoffice problem, referring to an application of assigning a residence to the nearest post office.
Contents 
The nearest neighbor search problem arises in numerous fields of application, including:
Various solutions to the NNS problem have been proposed. The quality and usefulness of the algorithms are determined by the time complexity of queries as well as the space complexity of any search data structures that must be maintained. The informal observation usually referred to as the curse of dimensionality states that there is no generalpurpose exact solution for NNS in highdimensional Euclidean space using polynomial preprocessing and polylogarithmic search time.
The simplest solution to the NNS problem is to compute the distance from the query point to every other point in the database, keeping track of the "best so far". This algorithm, sometimes referred to as the naive approach, has a running time of O(Nd) where N is the cardinality of S and d is the dimensionality of S. There are no search data structures to maintain, so linear search has no space complexity beyond the storage of the database. Surprisingly, naive search outperforms space partitioning approaches on higher dimensional spaces ^{[1]}.
Starting from 1970s branch and bound methodology was applied to the problem. In the case of Euclidean space this approach is known as spatial index or spatial access methods. Several spacepartitioning methods have been developed for solving the NNS problem. Perhaps the simplest is the kdtree, which iteratively bisects the search space into two regions containing half of the points of the parent region. Queries are performed via traversal of the tree from the root to a leaf by evaluating the query point at each split. Depending on the distance specified in the query, also neighboring branches that might contain hits need to be evaluated. For constant dimension query time, average complexity is O(log N) ^{[2]} in the case of randomly distributed points, worst case complexity analyses have been performed.^{[3]} Alternatively the Rtree data structure was designed to support nearest neighbor search in dynamic context, as it has efficient algorithms for insertions and deletions.
In case of general metric space branch and bound approach is known under the name of metric trees. Particular examples include VPtree and Bktree.
Locality sensitive hashing (LSH) is a technique for grouping points in space into 'buckets' based on some distance metric operating on the points. Points that are close to each other under the chosen metric are mapped to the same bucket with high probability.
The cover tree has a theoretical bound that is based on the dataset's doubling constant. The bound on search time is O(c^{12} log n) where c is the expansion constant of the dataset.
In high dimensional spaces tree indexing structures turn out to become useless because an increasing percentage of the nodes need to be examined anyway. To speed up linear search, a compressed version of the feature vectors stored in RAM is used to prefilter the datasets in a first run. The final candidates are determined in a second stage using the uncompressed data from the disk for distance calculation.^{[4]}
There are numerous variants of the NNS problem and the two most wellknown are the knearest neighbor search and the εapproximate nearest neighbor search.
knearest neighbor search identifies the top k nearest neighbors to the query. This technique is commonly used in predictive analytics to estimate or classify a point based on the consensus of its neighbors. knearest neighbor graphs are graphs in which every point is connected to its k nearest neighbors.
In some applications it may be acceptable to retrieve a "good guess" of the nearest neighbor. In those cases, we can use an algorithm which doesn't guarantee to return the actual nearest neighbor in every case, in return for improved speed or memory savings. Often such an algorithm will find the nearest neighbor in a majority of cases, but this depends strongly on the dataset being queried.
Algorithms which support the approximate nearest neighbor search include Best Bin First and Balanced BoxDecomposition Tree based search.^{[5]}
εapproximate nearest neighbor search is becoming an increasingly popular tool for fighting the curse of dimensionality.
Nearest neighbor distance ratio do not apply the threshold on the direct distance from the original point to the challenger neighbor but on a ratio of it depending on the distance to the previous neighbor. It is used in CBIR to retrieve pictures through a "query by example" using the similarity between local features. More generally it is involved in several matching problems.
For some applications (e.g. entropy estimation), we may have N datapoints and wish to know which is the nearest neighbor for every one of those N points. This could of course be achieved by running a nearestneighbor search once for every point, but an improved strategy would be an algorithm that exploits the information redundancy between these N queries to produce a more efficient search. As a simple example: when we find the distance from point X to point Y, that also tells us the distance from point Y to point X, so the same calculation can be reused in two different queries.
Given a fixed dimension, a semidefinite positive norm (thereby including every L^{p} norm), and n points in this space, the m nearest neighbours of every point can be found in O(mn log n) time.^{[6]}
