Nearest Neighbor Search (NNS) Task

From GM-RKB
(Redirected from nearest neighbor search)
Jump to navigation Jump to search

A Nearest Neighbor Search (NNS) Task is a similarity search task that requires finding item records in a metric space that are near a query point.



References

2020

  • (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Nearest_neighbor_search Retrieved:2020-5-5.
    • Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem 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 similar 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. Donald Knuth in vol. 3 of The Art of Computer Programming (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 metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, M is taken to be the d-dimensional vector space where dissimilarity is measured using the Euclidean distance, Manhattan distance or other distance metric. However, the dissimilarity function can be arbitrary. One example is asymmetric Bregman divergence, for which the triangle inequality does not hold.

2020


2007

2006