Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors.
Jonathan Derryberry, Donald R. Sheehy, Maverick Woo, Danny Sleator · 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 Lt-norm approximation ratio is O(d 1+1/t), and the running time for a query q is O(d 2 lg δ(p, q)), where p is the result of the preceding query and δ(p, q) is the number of input points in a suitably-sized box containing p and q. Our data structure has O(dn) 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 δ depends on d, and our results rely on the Random Access Machine (RAM) model with word size Θ(lg n). 1