@Inproceedings {export:73855,
abstract = {This work investigates a geometric approach to proving cell probe lower bounds
for data structure problems.

We consider the **approximate nearest neighbor search problem** on the Boolean
hypercube *(bool*^{d},onenorm {\cdot}) with *d=Θ(log n)*. We
show that any (randomized) data structure for the problem that answers
*c*-approximate nearest neighbor search queries using *t* probes must
use space at least *n*^{1+Ω(1/ct)}. In particular, our bound
implies that any data structure that uses space *˜O(n)* with
polylogarithmic word size, and with constant probability gives a constant
approximation to nearest neighbor search queries must be probed *Ω(log
n/ log log n)* times. This improves on the lower bound of *Ω(log log
d/log log log d)* probes shown by Chakrabarti and Regev for any polynomial
space data structure, and the *Ω(log log d)* lower bound in Patrascu
and Thorup for linear space data structures.

Our lower bound holds for the **near neighbor problem**, where the
algorithm knows in advance a good approximation to the distance to the nearest
neighbor.

Additionally, it is an **average case** lower bound for the natural
distribution for the problem. Our approach also gives the same bound for
*(2-frac 1c)*-approximation to the farthest neighbor problem.

For the case of non-adaptive algorithms we can improve the bound slightly and
show a *Ω(log n)* lower bound on the time complexity of data
structures with *O(n)* space and logarithmic word size.

We also show similar lower bounds for the partial match problem: any
randomized *t*-probe data structure that solves the partial match problem on
*{0,1,star }*^{d} for *d=Θ(log n)* must use space
*n*^{1+Ω(1/t)}. This implies an *Ω(log n/log log
n)* lower bound for time complexity of near linear space data structures,
slightly improving the *Ω(log n /(log log n)*^{2}) lower
bound from, for this range of *d*. Recently and independently Patrascu
achieved similar bounds . Our results also generalize to approximate partial
match, improving on the bounds of .

},
author = {Rina Panigrahy and Kunal Talwar and Udi Wieder},
booktitle = {FOCS '08: Proceedings of the 49th annual IEEE Symposium on Foundations of
Computer Science},
isbn = {978-0-7695-3436-7},
month = {October},
pages = {414–423},
publisher = {IEEE},
title = {A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and
Partial Match},
url = {http://research.microsoft.com/apps/pubs/default.aspx?id=73855},
year = {2008},
}