Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems
Allan Borodin, Rafail Ostrovsky, Yuval Rabani
Abstract: The curse of dimensionality describes the phenomenon whereby (in spite of extensive and continuing research) for various geometric search problems we only have algorithms with performance that grows exponentially in the dimension. Recent results [Kle97,IM98,KOR98] show that in some sense it is possible to avoid the curse of dimensionality for the approximate nearest neighbor search problem. But must the exact nearest neighbor search problem suffer this curse? We provide some evidence in support of the curse. Specifically we investigate the exact nearest neighbor search problem and the related problem of exact partial match within the asymmetric communication model first used by Miltersen [Mil93] to study data structure problems. We derive non-trivial asymptotic lower bounds for the exact problem that stand in contrast to known algorithms for approximate nearest neighbor search.
comment:
In Discrete and Computational Geometry - The Goodman-Pollack Festschrift. Algori
thms and Combinatorics Series 3143, Springer Verlag, Berlin, August 2003, pages
252-274.
Preliminary version in Proceedings of
The 31'st ACM Symposium on Theory of Computing (STOC-99)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |