Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-055 | 9th April 2019 15:38

Lower Bounds for Oblivious Near-Neighbor Search

RSS-Feed




TR19-055
Authors: Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
Publication: 9th April 2019 23:12
Downloads: 86
Keywords: 


Abstract:

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for ANN. This is the first super-logarithmic $\mathit{unconditional}$ lower bound for ANN against general (non black-box) data structures. We also show that any oblivious $\mathit{static}$ data structure for decomposable search problems (like ANN) can be obliviously dynamized with $O(\log n)$ overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).



ISSN 1433-8092 | Imprint