Nearest neighbor search
lastmod 2025-01-06created 2025-01-063 edits
Nearest neighbor search is an optimization problem of finding the closest (or most similar) point. It is also called proximity search, similarity search, or the closest point search problem. Closeness is generally expressed by a dissimilarity function, whose value grows larger the less similar two objects are. Formally, the nearest neighbor search problem is defined as follows: given a set S of points in a space M and a query point q ∈ M, find the point in S closest to q. Donald Knuth, in volume 3 of his book The Art of Computer Programming (1973), named it the post-office problem, referring to a program that assigns people's residences to the nearest post office. A direct generalization of this problem is the k-nearest neighbors algorithm, which finds the k closest points.
Generally, M is a metric space and dissimilarity is expressed by a distance metric that is symmetric and satisfies the triangle inequality. More commonly still, M is a d-dimensional vector space and dissimilarity is measured using Euclidean distance, Manhattan distance, and so on. However, since the dissimilarity function can be arbitrary, it can also be defined using, for example, the Bregman divergence, which is not symmetric and does not satisfy the triangle inequality.