LIPIcs.ICALP.2016.84.pdf
- Filesize: 495 kB
- 13 pages
Document
Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities
Author
-
Part of:
Volume:
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-23
Cite AsGet BibTex
Yitong Yin. Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 84:1-84:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.84
https://doi.org/10.4230/LIPIcs.ICALP.2016.84
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.
Keywords
- nearest neighbor search
- approximate near-neighbor
- cell-probe model
- isoperimetric inequality
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads