An optimal algorithm for approximate nearest neighbor searching fixed dimensions

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. Give...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 1998-11, Vol.45 (6), p.891-923
Main Authors: Arya, Sunil, Mount, David M, Netanyahu, Nathan S, Silverman, Ruth, Wu, Angela Y
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Computation
Data points
Integers
Mathematical models
Optimization
Query processing
Searching
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0004-5411
1557-735X
DOI:10.1145/293347.293348