Skip to main content
Vansh Verma
← Lab

minhash

confirmedshipRust · CPU · Apple M4Systems & data structuresJuly 14, 2026

the question

Does MinHash's Jaccard intersection error scale as 1/sqrt(overlap) independently of set size, beating HyperLogLog inclusion-exclusion at matched space by a margin that widens as overlap shrinks?

what came out

At matched space (MinHash k=1024 ~8 KB vs HLL 2^13 ~6 KB, n=1e6), MinHash wins at every overlap: 13x lower relative error at 0.1% overlap, narrowing to 1.6x at 30%. MinHash degrades as 1/sqrt and its error is set-size independent, where HLL degrades as 1/overlap.

method & receipts

  • Result: confirmed
  • Pre-registered — the prediction was written down and committed before the run.
  • Reproducible — one script re-runs the whole thing from scratch.
  • Tested — a correctness/benchmark suite ships alongside the code.

→ read the code and re-run it

github.com/v-code01/minhash