Nearest neighbor search
From Wikipedia, the free encyclopedia
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 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 d-dimensional 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 post-office problem, referring to an application of assigning a residence to the nearest post office.
Contents |
[edit] Applications
The nearest neighbor search problem arises in numerous fields of application, including:
- Pattern recognition - in particular for optical character recognition
- Statistical classification- see k-nearest neighbor algorithm
- Computer vision
- Databases - e.g. content-based image retrieval
- Coding theory - see maximum likelihood decoding
- Data compression - see MPEG-2 standard
- Recommendation systems
- Internet marketing - see contextual advertising and behavioral targeting
- DNA sequencing
- Spell checking - suggesting correct spelling
- Plagiarism detection
- Contact searching algorithms in FEA
- Similarity scores for predicting career paths of professional athletes.
[edit] Methods
Various solutions to the NNS problem have been proposed. The quality and usefulness of the algorithm are determined by the time complexity of queries as well as the space complexity of any search data structures that must be maintained. Informal observation usually referred as curse of dimensionality states that there is no general-purpose exact solution for NNS in high-dimensional Euclidean space using polynomial preprocessing and polylogarithmic search time.
[edit] Linear search
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, works for small databases but quickly becomes intractable as either the size or the dimensionality of the problem becomes large. Linear search 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.
[edit] Space partitioning
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 space-partitioning methods have been developed for solving the NNS problem. Perhaps the simplest is the kd-Tree, 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. For constant dimension query time complexity is O(log N). R-tree data structure was designed to support nearest neighbor search in dynamic context. 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 VP-tree and Bk-tree.
[edit] Locality sensitive hashing
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.
[edit] Nearest neighbor search in spaces with small intrinsic dimension
The cover tree has a theoretical bound that is based on the dataset's doubling constant. The bound on search time is O(c12 log n) where c is the expansion constant of the dataset.
[edit] Variants
There are numerous variants of the NNS problem and the two most well-known are the k-nearest neighbor search and the ε-approximate nearest neighbor search.
- k-nearest 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.
- ε-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.
[edit] See also
- K-nearest neighbor algorithm
- Nearest-neighbor interpolation
- Content-based image retrieval
- Near Duplicate Algorithms
- Locality sensitive hashing
- Voronoi diagram
[edit] References
- Arya, S., D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions. Journal of the ACM, vol. 45, no. 6, pp. 891-923
- Zezula, P., Amato, G., Dohnal, V., and Batko, M. Similarity Search - The Metric Space Approach. Springer, 2006. ISBN: 0-387-29146-6
[edit] External links
- Nearest Neighbors and Similarity Search - a website dedicated to educational materials, software, literature, researchers, open problems and events related to NN searching. Maintained by Yury Lifshits.
- Metric Spaces Library - An open-source C-based library for metric space indexing by Karina Figueroa, Gonzalo Navarro, Edgar Chávez.
- ANN - A Library for Approximate Nearest Neighbor Searching by David M. Mount and Sunil Arya.
- STANN - A Simple Threaded Approximate Nearest Neighbor Search Library in C++ by Michael Connor and Piyush Kumar.
- MESSIF - Metric Similarity Search Implementation Framework by Michal Batko and David Novak.
