Nearest Neighbor Search

Nearest neighbor search is the optimization problem of finding the point within a given set that is closest, by some measure of dissimilarity, to a given query point. Donald Knuth called it the post-office problem, by analogy with assigning a residence to its nearest post office; a natural generalization, k-nearest neighbor search, finds the k closest points rather than just one. Most practical implementations work in a metric space, where dissimilarity is expressed through a distance function such as Euclidean or Manhattan distance, though some methods use dissimilarity measures that are not true metrics. The problem underlies techniques across many fields, including pattern recognition, statistical classification, computer vision, computational geometry, cryptanalysis, database retrieval, DNA sequencing, spell checking, plagiarism detection, cluster analysis and, more recently, vector databases and retrieval-augmented generation systems built on embeddings.