Access Restriction

Author Arya, Sunil ♦ Malamatos, Theocharis ♦ Mount, David M.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Nearest neighbor searching ♦ Space-time tradeoffs
Abstract Nearest neighbor searching is the problem of preprocessing a set of $\textit{n}$ point points in $\textit{d}-dimensional$ space so that, given any query point $\textit{q},$ it is possible to report the closest point to $\textit{q}$ rapidly. In approximate nearest neighbor searching, a parameter ϵ > 0 is given, and a multiplicative error of (1 + ϵ) is allowed. We assume that the dimension $\textit{d}$ is a constant and treat $\textit{n}$ and ϵ as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space solutions having space $\textit{O}(\textit{n})$ and query time $\textit{O}(log$ $\textit{n}$ + $1/ϵ^{d™1})$ to high-space solutions having space roughly $\textit{O}((\textit{n}$ log $n)/ϵ^{d})$ and query time $\textit{O}(log$ $(\textit{n}/ϵ)).$ We show that there is a single approach to this fundamental problem, which both improves upon existing results and spans the spectrum of space-time tradeoffs. Given a tradeoff parameter γ, where 2 ≤ γ ≤ 1/ϵ, we show that there exists a data structure of space $O(nγ^{d™1}$ log(1/ϵ)) that can answer queries in time $\textit{O}(log(\textit{n}γ)$ + $1/(ϵγ)^{(d™1)/2}.$ When γ = 2, this yields a data structure of space $\textit{O}(\textit{n}$ log (1/ϵ)) that can answer queries in time $\textit{O}(log$ $\textit{n}$ + $1/ϵ^{(d™1)/2}).$ When γ = 1/ϵ, it provides a data structure of space $O((n/ϵ^{d™1})log(1/ϵ))$ that can answer queries in time $\textit{O}(log(\textit{n}/ϵ)).$ Our results are based on a data structure called a $(\textit{t},ϵ)-AVD,$ which is a hierarchical quadtree-based subdivision of space into cells. Each cell stores up to $\textit{t}$ representative points of the set, such that for any query point $\textit{q}$ in the cell at least one of these points is an approximate nearest neighbor of $\textit{q}.$ We provide new algorithms for constructing AVDs and tools for analyzing their total space requirements. We also establish lower bounds on the space complexity of AVDs, and show that, up to a factor of $\textit{O}(log$ (1/ϵ)), our space bounds are asymptotically tight in the two extremes, γ = 2 and γ = 1/ϵ.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 57
Issue Number 1
Page Count 54
Starting Page 1
Ending Page 54

Open content in new tab

   Open content in new tab
Source: ACM Digital Library