An optimal algorithm for approximate nearest neighbor searching fixed dimensions

TitleAn optimal algorithm for approximate nearest neighbor searching fixed dimensions
Publication TypeJournal Articles
Year of Publication1998
AuthorsArya S, Mount D, Netanyahu NS, Silverman R, Wu AY
JournalJournal of the ACM (JACM)
Volume45
Issue6
Pagination891 - 923
Date Published1998/11//
ISBN Number0004-5411
KeywordsApproximation 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.

URLhttp://doi.acm.org/10.1145/293347.293348(link is external)
DOI10.1145/293347.293348(link is external)