Lower Bounds for Oblivious Near-Neighbor Search
This addresses the problem of understanding computational limits for oblivious data structures in near-neighbor search, providing foundational theoretical insights for researchers in algorithms and data structures.
The paper proves an Ω(d lg n/(lg lg n)^2) lower bound on the dynamic cell-probe complexity of statistically oblivious approximate near-neighbor search over the d-dimensional Hamming cube, with a quadratic improvement to Ω̃(lg^2 n) for d = Θ(log n), and shows that any oblivious static data structure for decomposable problems can be dynamized with O(log n) overhead.
We prove an $Ω(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search ($\mathsf{ANN}$) over the $d$-dimensional Hamming cube. For the natural setting of $d = Θ(\log n)$, our result implies an $\tildeΩ(\lg^2 n)$ lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for $\mathsf{ANN}$. This is the first super-logarithmic $\mathit{unconditional}$ lower bound for $\mathsf{ANN}$ against general (non black-box) data structures. We also show that any oblivious $\mathit{static}$ data structure for decomposable search problems (like $\mathsf{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).