Approximate nearest neighbor queries revisited

This paper proposes new methods to answer approximate nearest neighbor queries on a set of n points in d-dimensional Euclidean space. For any fixed constant d, a data structure with O(ε^(1-d)/2n log n) preprocessing time and O(ε^(1-d)/2 log n) query time achieves an approximation factor 1 + ε for any given 0 < ε < 1; a variant reduces the ε-dependence by a factor of ε^-1/2. For any arbitrary d, a data structure with O(d²n log n) preprocessing time and O(d² log n) query time achieves an approximation factor O(d^3/2). Applications to various proximity problems are discussed.