Lower bound on the complexity of approximate nearest-neighbor searching on the hamming cube

Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov

Research output: Contribution to journalConference article

30 Scopus citations

Abstract

We consider the nearest-neighbor problem over the d-cube: given a collection of points in {0, 1}d, find the one nearest to a query point (in the L1 sense). We establish a lower bound of Ω(log log d/log log log d) on the worst-case query time. This result holds in the cell probe model with (any amount of) polynomial storage and word-size dO(1). The same lower bound holds for the approximate version of the problem.

Original languageEnglish (US)
Pages (from-to)305-311
Number of pages7
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1999
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Lower bound on the complexity of approximate nearest-neighbor searching on the hamming cube'. Together they form a unique fingerprint.

  • Cite this