A SIMPLE ALGORITHM FOR NEAREST-NEIGHBOR SEARCH IN HIGH DIMENSIONS

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 exponen tially with dimension, making them impractical for dimensionality abov e 15. In nearly all applications, the closest point is of interest onl y if it lies within a user-specified distance E. We present a simple a nd practical algorithm to efficiently search for the nearest neighbor within Euclidean distance E. The use of projection search combined wit h a novel data structure dramatically improves performance in high dim ensions. A complexity analysis is presented which helps to automatical ly determine epsilon in structured problems. A comprehensive set of be nchmarks clearly shows the superiority of the proposed algorithm for a Variety of structured and unstructured search problems. Object recogn ition is demonstrated as an example application. The simplicity of the algorithm makes it possible to construct an inexpensive hardware sear ch engine which can be 100 times faster than its software equivalent. A C++ implementation of our algorithm is available upon request to sea rch@cs.columbia.edu/CAVE/.