An optimal algorithm for approximate nearest neighbor searching fixed dimensions

TLDR

The problem is to find approximate nearest neighbors in d‑dimensional space under any Minkowski metric, where a point is a (1+ε)-approximate neighbor if its distance is within a factor (1+ε) of the true nearest neighbor. They construct a data structure that, after preprocessing, allows rapid retrieval of the nearest neighbor for any query point. The algorithm preprocesses n points in O(d n log n) time and O(d n) space, then returns a (1+ε)-approximate nearest neighbor in O(c_{d,ε} log n) time (c_{d,ε} ≤ d⌈1+6d/ε⌉^d) and can compute the k nearest neighbors in an additional O(k d log n) time.

Abstract

Consider a set of 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 ∈ R d , is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)- approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) 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 ∈ R d , and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O ( c d , ϵ log n ) time, where c d,ϵ ≤ d ⌈1 + 6d/ϵ⌉ d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n ) time.