Optimal Las Vegas Approximate Near Neighbors in ${\mathrm{\ell }}_p$

We show that approximate near neighbor search in high dimensions can be solved in a Las Vegas fashion (i.e., without false negatives) for ${\mathrm{\ell }}_p$ ($1\le p\le 2$) while matching the performance of optimal locality-sensitive hashing. Specifically, we construct a data-independent Las Vegas data structure with query time $O(d{n}^{\rho })$ and space usage $O(d{n}^{1+\rho })$ for $(r, c r)$-approximatenearneighborsin$$\mathbb{R}$^{d}$underthe$\ell_p$ norm, where $\rho =1\mathrm{/}{c}^p+o(1)$. Furthermore, we give a Las Vegas locality-sensitive filter construction for the unit sphere that can be used with the data-dependent data structure of Andoni et al. (SODA 2017) to achieve optimal space-time tradeoffs in the data-dependent setting. For the symmetric case, this gives us a data-dependent Las Vegas data structure with query time $O(d{n}^{\rho })$ and space usage $O(d{n}^{1+\rho })$ for $(r,cr)$-approximate near neighbors in ${\mathbb{R}}^d$ under the ${\mathrm{\ell }}_p$ norm, where $\rho = 1/(2c^p -

1. • o(1)$. Our data-independent construction improves on the recent Las Vegas data structure of Ahle (FOCS 2017) for ${\mathrm{\ell }}_p$ when $1<p\le 2$. Our data-dependent construction does even better for ${\mathrm{\ell }}_p$ for all $p\in [1,2]$ and is the first Las Vegas approximate near neighbors data structure to make use of data-dependent approaches. We also answer open questions of Indyk (SODA 2000), Pagh (SODA 2016), and Ahle by showing that for approximate near neighbors, Las Vegas data structures can match state-of-the-art Monte Carlo data structures in performance for both the data-independent and data-dependent settings and across space-time tradeoffs.