An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Title | An optimal algorithm for approximate nearest neighbor searching fixed dimensions |
Publication Type | Journal Articles |
Year of Publication | 1998 |
Authors | Arya S, Mount D, Netanyahu NS, Silverman R, Wu AY |
Journal | Journal of the ACM (JACM) |
Volume | 45 |
Issue | 6 |
Pagination | 891 - 923 |
Date Published | 1998/11// |
ISBN Number | 0004-5411 |
Keywords | Approximation algorithms, Box-decomposition trees, closet-point queries, nearest neighbor searching, post-office problem, priority search |
Abstract | Consider a set of 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 &egr;, data point p is a (1 +&egr;)-approximate nearest neighbor of q if its distance from q is within a factor of (1 + &egr;) 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 &egr; > 0, a (1 + &egr;)-approximate nearest neighbor of q can be computed in O(cd, &egr; log n) time, where cd,&egr;≤d 1 + 6d/e;d is a factor depending only on dimension and &egr;. In general, we show that given an integer k ≥ 1, (1 + &egr;)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n) time. |
URL | http://doi.acm.org/10.1145/293347.293348(link is external) |
DOI | 10.1145/293347.293348(link is external) |