Leading Zeros

HyperLogLog, one arrival at a time. Every item is hashed to 32 bits; the top p bits pick a register, and the run of leading zeros in what’s left is the evidence, because a run of k zeros turns up about once every 2^k hashes. Each register keeps the longest run it has ever seen — a max, which is the whole reason this works on a stream you cannot afford to deduplicate.

Three things are worth watching, in this order.

One register shouts. Start at 1 register and the estimate is 2^M, the longest run seen. It is not merely inaccurate, it is quantised: 8,192 or 16,384 or 65,536 and never anything in between, because powers of two are the only answers it has. One unusually long run early in the stream pins it there for the next twenty thousand items, and the error curve decays hyperbolically toward zero and then jumps the moment M ticks up — a sawtooth that is the shape of an estimator with a sample size of one.

A thousand registers whisper. Switch to m registers and the same evidence, split across 1024 slots and averaged with a harmonic mean, walks in toward the truth and stays there. The header states the promise — 1.04/√1024 = ±3.25% — and the curve settles inside it.

Then the promise gets checked. A single run landing inside the band proves nothing about the next one, so the error band is not something this piece asks you to take on faith. reroll hash ⟳ replays the same stream with a fresh hash and keeps the old curve; +10 runs does it ten times at once. The band fills in with curves until the envelope is visibly the one the formula named. That is the difference between a standard error and a number in a header: the error is a property of the hash, not of the data, and it is a distribution rather than a value.

The merge is the reason this is in your database. merge two sketches runs two streams that never see each other’s items, sketches each one, and takes the per-register max. Three answers to “how many distinct across both?” sit side by side: the exact union, the merged sketch (within a few percent), and est(A) + est(B), which at 100% overlap is 110% too high because it counts every shared key twice. Two sketches, 1.5 KB between them, and the union comes out right. No exact set gives you that at any price — you would have to ship the sets themselves.

Two details the viz shows rather than asserts:

• Repeats are free. Set repeats to 90% and step through. When a key arrives for the second time it hashes to the same bits, lands in the same register, and carries the same ρ — and a max cannot be raised by a value it already contains, so the estimate does not move at all. Plotted against the distinct count, the error curve at 90% repeats is identical to the one at 0%. The structure never needed to remember whether it had seen you.
• Two regimes, and which one is running is visible. Early on most of the field is empty, and the empty registers are better evidence than the harmonic mean is: the estimator switches to counting them, m·ln(m/V). The field’s label line says which regime is live, so the switch is a thing you watch happen rather than a branch you read about.

Reuse

src/leading-zeros.js is a framework-free ES module:

• hash32(str, seed) — FNV-1a plus murmur3’s fmix32 avalanche. Seeded, deliberately: rerolling the hash while holding the stream fixed is the experiment the demo is built around.
• registerOf(h, p) / rhoOf(h, p) — the index bits and 1 + the leading zeros of the remainder, capped at 33 − p.
• newSketch(p) / observe(sk, j, rho) / estimate(sk) — a sketch as plain state (register array, running harmonic-mean denominator, count of empties) so the update is one readable branch. observe returns whether the register actually moved.
• mergeSketches(a, b) — the per-register max.
• estimateFrom({m, p, z, zeros, maxReg}) — α_m·m²/z, the linear-counting small-range branch, and the degenerate 2^M single-register case.
• alpha(m), stdError(m), memoryBytes(m), exactBytes(n).
• simulate({mode, p, dup, overlap, items, seed, hashSeed}) — the run as frames, one per arrival, each carrying which register, what run, whether it moved, the exact truth and the estimate at that point. Same frame-per-tick shape as alignment, change, rho and window.
• registersAt(run, k) — register state after arrival k. A max is order-independent, so this is a scan rather than a replay, which is why frames don’t each carry a copy of the array.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

• The estimator is only as honest as the hash. Before trusting any of this on screen I checked the hash empirically: χ² = 245 on 256 registers over 20,000 keys (expect 255 ± 23), a ρ histogram tracking 2^−k, mean bias ≈ 0 at every m, and observed spread across 60 seeds matching 1.04/√m to within a few percent with ~41/60 runs inside 1σ. A viz of a sketch that silently used a bad hash would be a very convincing lie.
• 32-bit hashes cap ρ at 33 − p and would need the large-range correction past ~143M distinct; the demo stops at 20,000 arrivals, so it never gets there. Real implementations use 64-bit hashes and skip that correction entirely.
• seed fixes the stream and hashSeed fixes the hash — they are separate on purpose. Rerolling only the hash is what makes the error band checkable; rerolling the stream too would confound the two.
• Ghost curves are cleared when a parameter that changes the meaning of the band changes (register count, mode, overlap), but kept across a change of repeat rate — because the whole claim there is that the curve doesn’t move.
• The demo bundles its own copy of leading-zeros.js (self-contained by contract); re-copy after editing src/.