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

Amit Chakrabarti; Bernard Chazelle; Benjamin Gum; Alexey Lvov

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 journal › Conference article › peer-review

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¹ 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 - 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

Cite this

@article{d0681f1adedf4592bdf60676d26f667c,

title = "Lower bound on the complexity of approximate nearest-neighbor searching on the hamming cube",

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.",

author = "Amit Chakrabarti and Bernard Chazelle and Benjamin Gum and Alexey Lvov",

year = "1999",

language = "English (US)",

pages = "305--311",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 ; Conference date: 01-05-1999 Through 04-05-1999",

}

TY - JOUR

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

AU - Chakrabarti, Amit

AU - Chazelle, Bernard

AU - Gum, Benjamin

AU - Lvov, Alexey

PY - 1999

Y1 - 1999

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

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

UR - http://www.scopus.com/inward/record.url?scp=0032672872&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032672872&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0032672872

SN - 0734-9025

SP - 305

EP - 311

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99

Y2 - 1 May 1999 through 4 May 1999

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this