hllint

confirmedshipRust · CPUSystems & data structuresJuly 14, 2026

the question

Is HyperLogLog's inclusion-exclusion intersection estimate accurate for small overlaps between large sets?

what came out

Inclusion-exclusion on HLLs carries a near-constant absolute error floor around 7,000-8,500, independent of the true overlap. Relative error is 80x at a 0.01% overlap, 8x at 0.1%, still 79% at 1%, and only falls to a few percent once the overlap exceeds about 10% of the set.

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/hllint