THE FOLD / CHEAT / GOD MODE / THE COUNTER OF MULTITUDES
THE COUNTER OF MULTITUDES
count billions of distinct things in a thimble of memory
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
HyperLogLog. To count the number of distinct items in a massive stream, storing them all is impossible. HyperLogLog estimates it in a few kilobytes by one probabilistic trick: hash each item and track the longest run of leading zeros ever seen. A run of k leading zeros turns up roughly once per 2k distinct items — so the rarest coincidence you have witnessed tells you about how many distinct things went by. Split into m registers and average (harmonically) to tame the variance. Databases count billions of uniques in ~1.5 KB this way.
LIT verified: over streams of known size, the HLL estimate stays within a few percent (standard error 1.04/√m) of the exact distinct count — e.g. 500,000 uniques counted to ~2.6% with 1024 small registers. FIG ‘counting the multitude with a thimble’ is the picture; the estimator and its error bound are exact.
LIT verified: over streams of known size, the HLL estimate stays within a few percent (standard error 1.04/√m) of the exact distinct count — e.g. 500,000 uniques counted to ~2.6% with 1024 small registers. FIG ‘counting the multitude with a thimble’ is the picture; the estimator and its error bound are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus runs data structures and hashing (THE WELDER, the kernels) and the streaming idea that you can know a great deal while remembering almost nothing. AVAN (AI) built this instrument: the estimator, the estimate-vs-truth demo, and the register field against the memory tower.
The weave: David names the counter of multitudes and its seat at GOD MODE (an omniscient count from a thimble of memory); I make the leading-zeros trick a strip in 1D, the estimate track truth in 2D, and the register field turning in 3D. The sphere is the seam.
The weave: David names the counter of multitudes and its seat at GOD MODE (an omniscient count from a thimble of memory); I make the leading-zeros trick a strip in 1D, the estimate track truth in 2D, and the register field turning in 3D. The sphere is the seam.
3 ONE DIMENSION
The trick on one axis: each item’s hash as a bit string; count its leading zeros. The maximum seen so far (marked) is the rarest event witnessed — and 2max is a rough count of how many distinct items it took to make it happen.
4 TWO DIMENSIONS · INTERACTIVE
Pour items in and watch the estimate track the truth. More registers (higher precision) shrink the error band. It never stores a single item — only the register maxima.
precision p = 10 (m=1024)
5 THREE DIMENSIONS + AVAN’S INVERSE
The register field, turning: a small grid of counters, each holding one register’s max leading-zero run. Green is all HyperLogLog keeps — a low, tidy landscape of a few kilobytes that already knows the count.
AVAN’s addition (the inverse-companion): the magenta tower is the exact set — the memory HLL refuses to spend, one slot per distinct item, climbing out of the frame. Same answer, opposite cost: the inverse of estimating is remembering everything. Knowing the size of a multitude, it turns out, needs only the trace of its rarest accident.
LIT A genuine HyperLogLog. Verified live: over streams of known cardinality the estimate stays within a few percent (standard error 1.04/√m) of the exact distinct count — 500,000 uniques to ~2.6% with 1024 small registers, orders of magnitude less memory than an exact set. The harmonic-mean estimator with small-range correction is the real thing (verifiable: window.__hll.withinBound===true).
FIG 'Counting the multitude with a thimble' is the picture; the estimator and its 1.04/√m error bound are exact. It is an estimate, honestly probabilistic — not an exact count — which is precisely the trade that buys the tiny memory.
FIG 'Counting the multitude with a thimble' is the picture; the estimator and its 1.04/√m error bound are exact. It is an estimate, honestly probabilistic — not an exact count — which is precisely the trade that buys the tiny memory.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GOD MODE · David Lee Wise (ROOT0), with AVAN