# Optimal Las Vegas Locality Sensitive Data Structures

arXiv: https://arxiv.org/abs/1704.02054 · HTML: https://mlsanity.com/paper/1704.02054/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2017.

## Built on by (most cited first, 1 of 1)

- [Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation](https://mlsanity.com/paper/2510.23039/) (2025)

## Abstract (arXiv)

We show that approximate similarity (near neighbour) search can be solved in high dimensions with performance matching state of the art (data independent) Locality Sensitive Hashing, but with a guarantee of no false negatives. Specifically, we give two data structures for common problems. For c-approximate near neighbour in Hamming space we get query time dn1/c+o(1) and space dn1+1/c+o(1) matching that of citeindyk1998approximate and answering a long standing open question from~citeindyk2000dimensionality and~citepagh2016locality in the affirmative. By means of a new deterministic reduction from ℓ1 to Hamming we also solve ℓ1 and ℓ2 with query time d2n1/c+o(1) and space d2 n1+1/c+o(1). For (s1,s2)-approximate Jaccard similarity we get query time dnρ+o(1) and space dn1+ρ+o(1), ρ=logfrac1+s12s1big/logfrac1+s22s2, when sets have equal size, matching the performance of~citetobias2016. The algorithms are based on space partitions, as with classic LSH, but we construct these using a combination of brute force, tensoring, perfect hashing and splitter functions `a la~citenaor1995splitters. We also show a new dimensionality reduction lemma with 1-sided error.