Nearest Neighbor Search 
 The problem of finding the closest point in highdimensional spaces is
common in pattern recognition. Unfortunately, the complexity of most existing
search algorithms, such as kd tree and Rtree, 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
userspecified 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. 9891003, Sep. 1997. [PDF] [bib] [©]
"Algorithms for Pattern Rejection," S. Baker and S.K. Nayar, IEEE International Conference on Pattern Recognition (ICPR), Vol. 2, pp. 869874, 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. 859865, Jun. 1996. [PDF] [bib] [©]
"Pattern Rejection," S. Baker and S.K. Nayar, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 544549, 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. 733737, Nov. 1994. [PDF] [bib] [©] [Main Project Page]

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

What is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images?
Appearance Matching
Parametric Feature Detection


