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.