Lower Bounds for Oblivious Near-Neighbor Search

Kasper Green Larsen, Tal Malkin, Omri Weinstein +1

We prove an $\Omega (d\lg n/(\lg \lg n{)}^2)$ lower bound on the dynamic cell-probe complexity of statistically $oblivious$ approximate-near-neighbor search ($\mathsf{ANN}$) over…