2016/02/17 by Yitong Yin, Yin, Yitong
Computer Science · Decision Sciences · #Advanced Image and Video Retrieval Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Multi-Criteria Decision Making
paper · pdf · doi:10.48550/arxiv.1602.05391
openalex publication_date 2016/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove an Ω(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 d-dimensional 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.