A companion result. HyperLogLog is exact for unions but its inclusion-exclusion intersection error grows like 1/overlap, so it is useless for the small-overlap case people most want (see the companion hllint study). MinHash is the standard alternative: it estimates the Jaccard similarity directly, and this repository shows, with exact ground truth and bootstrap CIs on an M4, that at matched space MinHash beats HLL for intersection by a margin that widens as the sets get more dissimilar, because MinHash degrades only like 1/sqrt(overlap) where HLL degrades like 1/overlap.
- MinHash's Jaccard estimate has variance J(1-J)/k, so its relative error is about 1/sqrt(J*k): it depends only on the Jaccard J and the width k, NOT on set size.
- HLL's inclusion-exclusion intersection has a constant absolute error floor about sigma*n, so its relative error is about 1/overlap.
Subtracting large noisy cardinalities (HLL) loses a fixed absolute amount of accuracy that the small intersection cannot absorb; sampling agreement directly (MinHash) keeps a fixed relative resolution per matched slot. As the overlap shrinks, 1/sqrt beats 1/linear by more and more.
| overlap | Jaccard | MinHash rel err (CI) | HLL rel err (CI) | MinHash advantage |
|---|---|---|---|---|
| 0.1% | 0.0005 | 1.00 [0.95, 1.00] | 13.1 [5.0, 23.2] | 13x |
| 0.3% | 0.0015 | 0.35 [0.30, 0.30] | 4.15 [2.05, 7.90] | 12x |
| 1% | 0.005 | 0.42 [0.03, 0.42] | 1.62 [0.82, 2.21] | 4x |
| 3% | 0.015 | 0.23 [0.04, 0.28] | 0.59 [0.24, 0.70] | 2.6x |
| 10% | 0.053 | 0.054 [0.002, 0.054] | 0.158 [0.083, 0.218] | 3x |
| 30% | 0.176 | 0.024 [0.009, 0.062] | 0.039 [0.020, 0.047] | 1.6x |
At matched space MinHash wins at every overlap, and the advantage grows as the overlap shrinks: 13x at a 0.1% overlap, narrowing to 1.6x at 30% (where both are accurate and the choice barely matters). Both estimators eventually fail for overlaps too small for their width to resolve, but MinHash's usable range extends far further because it degrades as a square root, not linearly.
If you need set intersections or similarity, especially between large sets with small overlaps (which segment/audience/dedup questions usually are), estimate the Jaccard with MinHash rather than subtracting HyperLogLog cardinalities. HLL stays the right tool for pure distinct counts and unions; it is the intersection, built by inclusion-exclusion, that it silently gets wrong, and MinHash is the fix whose error does not grow with your data.
./run.sh
Needs a recent Rust (edition 2021) and Python 3 (standard library only). CPU only, exact ground truth by construction. Numbers vary run to run but the ordering and the widening advantage do not.
src/lib.rs: MinHash (add / jaccard) and the HLL intersection baseline, with the correctness, size-independence, and head-to-head tests.src/bin/bench.rs: the intersection error measurement for both estimators.sweep.py: the Jaccard sweep with BCa aggregation (pure Python).PREREG.md: the pre-registration.run.sh: reproduces everything.
Apple M4, CPU only. n = 1e6, exact ground truth, roughly matched space. The claim is the scaling-law comparison (1/sqrt vs 1/linear) and MinHash's set-size independence, not exactness for arbitrarily tiny overlaps.
MIT.