✦ LIBER ✦

An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching

✍ Scribed by Chakrabarti, Amit; Regev, Oded

Book ID: 118181054
Publisher: Society for Industrial and Applied Mathematics
Year: 2010
Tongue: English
Weight: 319 KB
Volume: 39
Category: Article
ISSN: 0097-5397
DOI: 10.1137/080729955

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An optimal algorithm for approximate nea

An optimal algorithm for approximate nearest neighbor searching fixed dimensions

✍ Arya, Sunil; Mount, David M.; Netanyahu, Nathan S.; Silverman, Ruth; Wu, Angela 📂 Article 📅 1998 🏛 Association for Computing Machinery 🌐 English ⚖ 281 KB

An optimal algorithm for approximate nea

An optimal algorithm for approximate nearest neighbor searching fixed dimensions

✍ Arya, Sunil; Mount, David M.; Netanyahu, Nathan S.; Silverman, Ruth; Wu, Angela 📂 Article 📅 1998 🏛 Association for Computing Machinery 🌐 English ⚖ 281 KB

Tighter Lower Bounds for Nearest Neighbo

Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model

✍ Omer Barkol; Yuval Rabani 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 187 KB

We prove new lower bounds for nearest neighbor search in the Hamming cube. Our lower bounds are for randomized, two-sided error, algorithms in Yao's cell probe model. Our bounds are in the form of a tradeoff among the number of cells, the size of a cell, and the search time. For example, suppose we