| Achieving Spatial Adaptivity while Finding Approximate Nearest Neighbors (2009) | |||||||||||||||
Abstract | |||||||||||||||
| 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 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||