Nearest neighbor search

Nearest neighbor search (NNS), as a form of proximity search, is the <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less <a href="/facts/Similarity_measure/FmmFco8c">similar</a> the objects, the larger the function values. 
Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set S of points in a space M and a query point q ∈ M, find the closest point in S to q. <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a> in vol. 3 of <a href="/facts/The_Art_of_Computer_Programming/MR1bMD9e">The Art of Computer Programming</a> (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a k-NN search, where we need to find the k closest points.
Most commonly M is a <a href="/facts/Metric_space/gnBBRXtc">metric space</a> and dissimilarity is expressed as a <a href="/facts/Distance_metric/RkUptSo8">distance metric</a>, which is symmetric and satisfies the <a href="/facts/Triangle_inequality/KubLjkwr">triangle inequality</a>. Even more common, M is taken to be the d-dimensional <a href="/facts/Vector_space/M1pxMLx2">vector space</a> where dissimilarity is measured using the <a href="/facts/Euclidean_distance/9qDoQKQe">Euclidean distance</a>, <a href="/facts/Taxicab_geometry/zU7gGUPv">Manhattan distance</a> or other <a href="/facts/Statistical_distance/u6kgN8Dc">distance metric</a>. However, the dissimilarity function can be arbitrary. One example is asymmetric <a href="/facts/Bregman_divergence/wREwF8qo">Bregman divergence</a>, for which the triangle inequality does not hold.

Nearest neighbor search open-in-new

Nearest neighbor search