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(epsilon((1-d)/2n) log n) preprocessing time and O (epsilon((1-d)/2) log n) query time achieves an approximation factor 1 + epsilon for any given 0 < epsilon < 1; a variant reduces the E-dependence by a factor of epsilon(-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 an approximation factor O (d(3/2)). Applications to various proximity problems are discussed.