Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.84
URN: urn:nbn:de:0030-drops-62010
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6201/
Yin, Yitong
Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities
| pdf-format: |
|
Abstract
We prove an Omega(d/log(sw/nd)) lower bound for the average-case cell-probe complexity of deterministic or Las Vegas randomized algorithms solving approximate near-neighbor (ANN) problem in ddimensional Hamming space in the cell-probe model with w-bit cells, using a table of size s. This lower bound matches the highest known worst-case cell-probe lower bounds for any static data structure problems.This average-case cell-probe lower bound is proved in a general framework which relates the cell-probe complexity of ANN to isoperimetric inequalities in the underlying metric space. A tighter connection between ANN lower bounds and isoperimetric inequalities is established by a stronger richness lemma proved by cell-sampling techniques.
BibTeX - Entry
@InProceedings{yin:LIPIcs:2016:6201,
author = {Yitong Yin},
title = {{Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {84:1--84:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6201},
URN = {urn:nbn:de:0030-drops-62010},
doi = {10.4230/LIPIcs.ICALP.2016.84},
annote = {Keywords: nearest neighbor search, approximate near-neighbor, cell-probe model, isoperimetric inequality}
}
| Keywords: | nearest neighbor search, approximate near-neighbor, cell-probe model, isoperimetric inequality | |
| Seminar: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 23.08.2016 |
