An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions

Consider a set S of n data points in real d-dimensional space, Rd, 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 [ Rd, is the closest point of S to q can be reported quickly. Given any positive real e , a data point p is a (11 e )-approximate nearest neighbor of q if its distance from q is within a factor of (1 1 e ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in Rd in O(dn log n) time and O(dn) space, so that given a query point q [ Rd, and e . 0, a (11 e )-approximate nearest neighbor of q can be computed in O(cd, e log n) time, where cd, e # d 1 1 6d/ e d is a factor depending only on dimension and e . In general, we show that given an integer k $ 1, (1 1 e )-approximations to the k nearest neighbors of q can be computed in additional O(kd log n) time.