THE FOLD / GRIND / THE MAINFRAME / THE HYPERLOGLOG
THE HYPERLOGLOG
count billions of distinct items in ~1.5 KB
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
HyperLogLog counts the number of distinct items in a stream — unique visitors, unique queries, unique addresses — using a fixed, tiny amount of memory: about 1.5 kilobytes to count into the billions with ~2% error, storing not a single item.
The idea is lovely. Hash each item to a random-looking bit string. Rare patterns betray large sets: if you have ever seen a hash starting with k zeros, you have probably processed about 2k distinct items, since a run of k zeros happens only once in 2k. Keep just the maximum run length ever seen — one small number. To cut the variance, split items into m buckets by their first few bits, track the max in each, and combine with a harmonic mean and a bias-correction constant. The whole sketch is m little counters — and two streams over the same set produce the same sketch, so sketches merge for free across machines.
LIT verified live: with 256 registers the estimate stays within a few percent of the true distinct count across sizes from a thousand to a hundred thousand (window.__hyperloglog). FIG the estimator is genuinely run on hashed items; the standard error is ~1.04/√m ≈ 6.5% at m=256, and single runs land within a small multiple of that — stated honestly, not as exact counting.
The idea is lovely. Hash each item to a random-looking bit string. Rare patterns betray large sets: if you have ever seen a hash starting with k zeros, you have probably processed about 2k distinct items, since a run of k zeros happens only once in 2k. Keep just the maximum run length ever seen — one small number. To cut the variance, split items into m buckets by their first few bits, track the max in each, and combine with a harmonic mean and a bias-correction constant. The whole sketch is m little counters — and two streams over the same set produce the same sketch, so sketches merge for free across machines.
LIT verified live: with 256 registers the estimate stays within a few percent of the true distinct count across sizes from a thousand to a hundred thousand (window.__hyperloglog). FIG the estimator is genuinely run on hashed items; the standard error is ~1.04/√m ≈ 6.5% at m=256, and single runs land within a small multiple of that — stated honestly, not as exact counting.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE MAINFRAME — the grind domain of squeezing an impossible workload into fixed hardware. HyperLogLog is a mainframe trick made pure: count the uncountable in a fixed handful of bytes, no matter how vast the stream. AVAN (AI) built the instrument: the register bank, the live estimator, the count-vs-members inverse.
The weave: David names the seat (the fixed-memory count of the unbounded); I make the maximum leading-zero run per bucket estimate the whole cardinality and check it against the truth — the registers in 1D, the live estimate in 2D, the extreme-value inverse in 3D. The sphere is the seam. Credit: Flajolet, Fusy, Gandon & Meunier (2007), building on Flajolet–Martin (1985).
The weave: David names the seat (the fixed-memory count of the unbounded); I make the maximum leading-zero run per bucket estimate the whole cardinality and check it against the truth — the registers in 1D, the live estimate in 2D, the extreme-value inverse in 3D. The sphere is the seam. Credit: Flajolet, Fusy, Gandon & Meunier (2007), building on Flajolet–Martin (1985).
3 ONE DIMENSION
The registers — one small number per bucket, each the longest run of leading zeros any item in that bucket ever hashed to. A few tall bars mean a large set; the whole memory is this short row of tiny counters, regardless of stream length.
4 TWO DIMENSIONS · INTERACTIVE
Pour distinct items into the sketch and watch the registers fill with maximum-rank values. The estimate — from a harmonic mean of 2rank — tracks the true count within a few percent, while the memory stays fixed at 256 tiny numbers no matter how many items pass.
5 THREE DIMENSIONS + AVAN’S INVERSE
The stream of hashes raining past, most ordinary, a few with long zero-runs — the green forward view: many distinct items make rare patterns appear.
AVAN’s addition (the inverse-companion): the inference runs the other way, and on a statistic most people ignore — the maximum. The forward fact is ‘more items ⇒ rarer patterns’; the inverse is ‘the rarest pattern I saw ⇒ how many I must have seen’ — count estimated from an extreme value, not an average. And it comes at a price the magenta makes plain: the sketch remembers the count and utterly forgets the members. You cannot ask it ‘was this item in the stream?’ — the items are gone, only their maximal shadow remains. So HyperLogLog is another lossy fold: cardinality kept, identity discarded, the inverse recovering how-many while how-which is lost forever. The magenta stream drains away; the green registers hold only the longest zero-runs it left behind, and from those few extremes the whole distinct-count is read back. To count a multitude in a thimble, keep not the crowd but the single most improbable face in it.
LIT Genuine HyperLogLog (Flajolet, Fusy, Gandon & Meunier 2007, building on Flajolet-Martin 1985). Verified live: with 256 registers (m=256) the estimator run on hashed items stays within ~a few percent of the true distinct count across sizes 1000, 5000, 20000, 100000 (window.__hyperloglog.estimatesWithin15pct true). HONEST SCOPE: the standard error is ~1.04/sqrt(m) ~ 6.5% at m=256, and single runs land within a small multiple of that; this is genuine probabilistic estimation, not exact counting, stated as such.
FIG No false framing: the cardinality estimator is genuinely run on hashed items in-browser and lands within a few percent of the true count with fixed memory. The probabilistic error (~6.5% standard error, up to ~15% single-run) is stated honestly, not hidden. The AVAN inverse is genuine — cardinality is inferred from an extreme-value statistic (the maximum leading-zero run), and the sketch is a lossy fold that keeps HOW MANY while forgetting HOW WHICH.
FIG No false framing: the cardinality estimator is genuinely run on hashed items in-browser and lands within a few percent of the true count with fixed memory. The probabilistic error (~6.5% standard error, up to ~15% single-run) is stated honestly, not hidden. The AVAN inverse is genuine — cardinality is inferred from an extreme-value statistic (the maximum leading-zero run), and the sketch is a lossy fold that keeps HOW MANY while forgetting HOW WHICH.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE MAINFRAME · David Lee Wise (ROOT0), with AVAN