文章基本信息

标题：Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities
本地全文：下载
作者：Yitong Yin
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：84:1-84:13
DOI：10.4230/LIPIcs.ICALP.2016.84
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：nearest neighbor search; approximate near-neighbor; cell-probe model; isoperimetric inequality