## Abstract

We consider the approximate nearest neighbor search problem on the Hamming cube {0, 1}^{d}. We show that a randomized cell probe algorithm that uses polynomial storage and word size d^{O(1)} requires a worst case query time of Ω(loglog d/logloglog d). The approximation factor may be as loose as 2^{log 1-nd} for any fixed n ≤ 0. Our result fills a major gap in the study of this problem since all earlier lower bounds either did not allow randomization [A. Chakrabarti et al., A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, in Discrete and Computational Geometry, Springer, Berlin , 2003, pp. 313-328; D. Liu, Inform. Process. Lett., 92 (2004), pp. 23-29] or did not allow approximation [A. Borodin, R. Ostrovsky, and Y. Rabani, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 312-321; O. Barkol and Y. Rabani, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 388-396; T. S. Jayram et al., J. Comput. System Sci., 69 (2004), pp. 435-447]. We also give a cell probe algorithm that proves that our lower bound is optimal. Our proof uses a lower bound on the round complexity of the related communicat ion problem. We show, additionally, that considerations of bit complexity alone cannot prove any n ontrivial cell probe lower bound for the problem. This shows that the "richness technique" [P. B. Miltersen et al., J. Comput. System Sci., 57 (1998), pp. 37-49] 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 [A. Chakrabarti et al., Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001 , pp. 270-278; Z. Bar-Yossef et al., Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 209-218; P. Sen, Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 73-83; R. Jain, J. Radhakrishnan, and P. Sen, Proceedings of the 30th International Colloquium on Automata, Languages and Programming, 2003, pp. 300-315].

Original language | English (US) |
---|---|

Pages (from-to) | 1919-1940 |

Number of pages | 22 |

Journal | SIAM Journal on Computing |

Volume | 39 |

Issue number | 5 |

DOIs | |

State | Published - 2010 |

## Keywords

- Cell probe model
- Nearest neighbor search
- Round elimination

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics