The problem of finding the closest point in high-dimensional spaces is common in pattern recognition. Unfortunately, the complexity of most existing search algorithms, such as k-d tree and R-tree, grows exponentially with dimension, making them impractical for dimensionality above 15 or so. In nearly all applications, the closest point is of interest only if it lies within a user-specified distance e. We have developed a simple and practical algorithm to efficiently search for the nearest neighbor within Euclidean distance e. The use of projection search combined with a novel data structure dramatically improves performance in high dimensions. A complexity analysis has been done which aids in automatically determining e in structured problems. A comprehensive set of benchmarks clearly demonstrates the benefits of the proposed algorithm for a variety of structured and unstructured search problems. Object recognition by appearance matching is demonstrated as an example application. The simplicity of the algorithm makes it possible to construct an inexpensive hardware search engine which can be at least 100 times faster than its software equivalent. A C++ implementation of our algorithm has been made available.

Publications

"A Simple Algorithm for Nearest Neighbour Search in High Dimensions,"
S.A. Nene and S.K. Nayar,
IEEE Transactions on Pattern Analysis and Machine Intelligence,
Vol.19, No.9, pp.989-1003, Sep, 1997.
[PDF] [bib] [©]

"Algorithms for Pattern Rejection,"
S. Baker and S.K. Nayar,
IEEE International Conference on Pattern Recognition (ICPR),
Vol.2, pp.869-874, Aug, 1996.
[PDF] [bib] [©]

"Closest Point Search in High Dimensions,"
S.A. Nene and S.K. Nayar,
IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
pp.859-865, Jun, 1996.
[PDF] [bib] [©]

"Pattern Rejection,"
S. Baker and S.K. Nayar,
IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
pp.544-549, Jun, 1996.
[PDF] [bib] [©]

"SLAM: A Software Library for Appearance Matching,"
S.A. Nene, S.K. Nayar and H. Murase,
DARPA Image Understanding Workshop (IUW),
Vol.1, pp.733-737, Nov, 1994.
[PDF] [bib] [©]

Images

		The Approach: The nearest neighbor algorithm efficiently finds points inside a small hypercube of predefined size around the novel query point. The closest point is then found by performing an exhaustive search within the hypercube using the Euclidean distance metric.
		Data Structures Used by the Algorithm: The data structures used for constructing and trimming the candidate list which corresponds to points that lie within the hypercube placed around the query point. The point set in this picture corresponds to the raw list of data points, while in the ordered set each coordinate is sorted. The forward and backward maps enable efficient correspondence between the point and ordered sets.
		Proposed Implementation in Hardware: This picture shows a simple architecture that can be used to implement the search algorithm in hardware.

Software

NEARSEARCH: Nearest Neighbor Search

Related Projects

What is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images?

Appearance Matching

Parametric Feature Detection