Approximate nearest neighbor queries revisited
Timothy M. Chan · 1997
This paper proposes new methods to answer approximate nearest neighbor queries on a set of n points in d-dimensional Euclidean space. For any xed constant d, a data structure with O( " (1;d)=2 n log n) preprocessing time and O( " (1;d)=2 log n) query time achieves approximation factor 1 + " for any given 0 <"<1�avariant reduces the "-dependence by afactorof ";1=2.For any arbitrary d, a data structure with O(d 2 n log n) preprocessing time and O(d 2 log n) query time achieves approximation factor O(d 3=2). Applications to various proximity problems are discussed. 1