### Space-time tradeoffs for approximate nearest neighbor searchingSpace-time tradeoffs for approximate nearest neighbor searching

Access Restriction
Subscribed

 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

Source: ACM Digital Library