### 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 L^{1} 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 d^{O(1)}. The same lower bound holds for the approximate version of the problem.

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

Pages (from-to) | 305-311 |

Number of pages | 7 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

State | Published - Jan 1 1999 |

Event | Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA Duration: May 1 1999 → May 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

Chakrabarti, A., Chazelle, B., Gum, B., & Lvov, A. (1999). Lower bound on the complexity of approximate nearest-neighbor searching on the hamming cube.

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 305-311.