About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1997
Conference paper
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.