Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors

CCCG: The Canadian Conference in Computational Geometry
2008

We present the first spatially adaptive data structure that answers
approximate nearest neighbor (ANN) queries to points that reside in a
geometric space of any constant dimension $d$.

The $L_t$-norm approximation ratio is $O(d^{1 + 1/t})$, and the running time for a query $q$ is $O(d^2 \lg \delta(p, q))$, where $p$ is the result of the preceding query and $\delta(p, q)$ is the number of input points in a suitably-sized box containing $p$ and $q$.

Our data structure has $O(d n)$ size and requires $O(d^2 n \lg n)$ preprocessing time, where $n$ is the number of points in the data structure.

The size of the bounding box for $\delta$ depends on $d$, and our results rely on the Random Access Machine (RAM) model with word size $\Theta(\lg n)$.

The $L_t$-norm approximation ratio is $O(d^{1 + 1/t})$, and the running time for a query $q$ is $O(d^2 \lg \delta(p, q))$, where $p$ is the result of the preceding query and $\delta(p, q)$ is the number of input points in a suitably-sized box containing $p$ and $q$.

Our data structure has $O(d n)$ size and requires $O(d^2 n \lg n)$ preprocessing time, where $n$ is the number of points in the data structure.

The size of the bounding box for $\delta$ depends on $d$, and our results rely on the Random Access Machine (RAM) model with word size $\Theta(\lg n)$.

@inproceedings{derryberry08achieving, Author = {John Derryberry and Daniel D. Sleator and Donald Sheehy and Maverick Woo}, Booktitle = {CCCG: Canadian Conference in Computational Geometry}, Title = {Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors}, Year = {2008}}