# Set Similarity Search Beyond MinHash

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2016.

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

- [CodeShell Technical Report](https://mlsanity.com/paper/2403.15747/) (2024)
- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)
- [Minwise-Independent Permutations with Insertion and Deletion of Features](https://mlsanity.com/paper/2308.11240/) (2023)
- [Distributional Drift Detection in Medical Imaging with Sketching and Fine-Tuned Transformer](https://mlsanity.com/paper/2408.08456/) (2024)

## Abstract (arXiv)

We consider the problem of approximate set similarity search under Braun-Blanquet similarity B(x, y) = |x cap y| / max(|x|, |y|). The (b2, b2)-approximate Braun-Blanquet similarity search problem is to preprocess a collection of sets P such that, given a query set q, if there exists x ∈ P with B(q, x) ≥ b1, then we can efficiently return x' ∈ P with B(q, x') > b2. We present a simple data structure that solves this problem with space usage O(n1+ρlog n + sumx ∈ P|x|) and query time O(|q|nρ log n) where n = |P| and ρ = log(1/b1)/log(1/b2). Making use of existing lower bounds for locality-sensitive hashing by O'Donnell et al. (TOCT 2014) we show that this value of ρ is tight across the parameter space, i.e., for every choice of constants 0 < b2 < b1 < 1. In the case where all sets have the same size our solution strictly improves upon the value of ρ that can be obtained through the use of state-of-the-art data-independent techniques in the Indyk-Motwani locality-sensitive hashing framework (STOC 1998) such as Broder's MinHash (CCS 1997) for Jaccard similarity and Andoni et al.'s cross-polytope LSH (NIPS 2015) for cosine similarity. Surprisingly, even though our solution is data-independent, for a large part of the parameter space we outperform the currently best data-dependent method by Andoni and Razenshteyn (STOC 2015).