TR03-070 Authors: Amit Chakrabarti, Oded Regev

Publication: 24th September 2003 19:21

Downloads: 2596

Keywords:

We 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.