An optimal algorithm for approximate nearest neighbor searching in fixed dimensions

Consider a set S of n data points in real d-dimensional space, R-d, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q epsilon R-d, is the closest point of S to q can be reported quickly. Given any positive real epsilon, a data point p is a (1 + epsilon)-approximate nearest neighbor of q if its distance from q is within a factor of (1 + epsilon) Of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R-d in O(dn log n) time and O(dn) space, so that given a query point q epsilon R-d, and epsilon > 0, a (1 + epsilon)-approximate nearest neighbor of q can be computed in O(c(d,epsilon) log n) time, where c(d,epsilon) less than or equal to d [1 + 6d/epsilon](d) is a factor depending only on dimension and epsilon. In general, we show that given an integer k greater than or equal to 1 (1 + epsilon)-approximations to the k nearest neighbors of q cart be computed in additional O(kd log n) time.