Two algorithms for nearest-neighbor search in high dimensions

Abstract

The nearest neighbor problem ford-dimensional Eucledian space is studied to pre-process a database of n points so that given a query point, one can efficiently determine its nearest neighbor in the database. The approach is based on a method for combining randomly chosen one-dimensional projections of the underlying point set. The following results were obtained: (1) an algorithm for finding ε-approximate nearest neighbors with a query time of O((d log2 d)(d+log n)); and (2) an ε-approximate nearest neighbor algorithm with near linear storage and a query time that improves asymptotically on linear search in all dimensions.