An optimal algorithm for approximate nearest neighbor searching

Let S denote a set of n points in d-dimensional space, Rd, and let dist(p,q) denote the distance between two points in any Minkowski metric. For any real ε > 0 and q ∈ Rd, a point p ∈ S is a (1+ε)-approximate nearest neighbor of q if, for all p′ ∈ S, we have dist (p,q)/dist(p′,q)≤(1+ε). We show how to preprocess a set of n points in Rd in O(n log n) time and O(n) space, so that given a query point q ∈ Rd, and ε>0, a (1+ε)-approximate nearest neighbor of q can be computed in O(log n) time. Constant factors depend on d and ε. We show that given an integer k≥1, (1+ε)-approximations to the k-nearest neighbors of q can be computed in O(k log n) time.