ECCC-Report TR03-070https://eccc.weizmann.ac.il/report/2003/070Comments and Revisions published for TR03-070en-usWed, 24 Sep 2003 19:21:43 +0300
Paper TR03-070
| An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching |
Amit Chakrabarti,
Oded Regev
https://eccc.weizmann.ac.il/report/2003/070We consider the approximate nearest neighbour search problem on the
Hamming Cube $\b^d$. We show that a randomised cell probe algorithm that
uses polynomial storage and word size $d^{O(1)}$ requires a worst case
query time of $\Omega(\log\log d/\log\log\log d)$. The approximation
factor may be as loose as $2^{\log^{1-\eta}d}$ for any fixed $\eta >
0$. This generalises an earlier result on the
deterministic complexity of the same problem and, more importantly,
fills a major gap in the study of this problem since all earlier lower
bounds either did not allow randomisation
or did not allow approximation.
We also give a cell probe algorithm which proves that our lower bound is
optimal.
Our proof uses a lower bound on the round complexity of the
related communication problem. We show, additionally, that
considerations of bit complexity alone cannot prove any nontrivial cell
probe lower bound for the problem. This shows that the Richness
Technique used in a lot of recent research around
this problem would not have helped here.
Our proof is based on information theoretic techniques for communication
complexity, a theme that has been prominent in recent
research. In
particular, we make heavy use of the round elimination and message
compression ideas in the recent work of Sen and Jain,
Radhakrishnan, and Sen, and also introduce a new
technique which we call message switching.
Wed, 24 Sep 2003 19:21:43 +0300https://eccc.weizmann.ac.il/report/2003/070