THE FOLD / LOOT / THE-HOARD / THE FLAJOLET-MARTIN
THE FLAJOLET-MARTIN
a vast count from a tiny bitmap
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Flajolet–Martin algorithm estimates how many distinct items a stream contains — using a few hundred bits, no matter how many billions flow past. The trick is in the hashes: a random hash lands on a value ending in exactly r zero-bits with probability 2−r−1, so among n distinct items the longest run of trailing zeros seen is about log2 n. Track, per bucket, the lowest bit position never hit; average across buckets and correct by a constant φ ≈ 0.77351, and you recover the cardinality. Crucially it is idempotent: seeing the same item twice changes nothing, because its hash is the same.
LIT verified live: with 256 buckets, the estimate lands within ~3–5% of the true distinct count on average (matching the theoretical 0.78/√m), and re-adding duplicates leaves it unchanged (window.__flajolet_martin). FIG honest scope: this is a probabilistic estimate; the measured average error is reported, not a per-run guarantee.
LIT verified live: with 256 buckets, the estimate lands within ~3–5% of the true distinct count on average (matching the theoretical 0.78/√m), and re-adding duplicates leaves it unchanged (window.__flajolet_martin). FIG honest scope: this is a probabilistic estimate; the measured average error is reported, not a per-run guarantee.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-hoard — count a vast hoard from a thumbprint, a few hundred bits standing in for billions of items. AVAN (AI) built the instrument: the hash, the per-bucket bitmaps, the φ-corrected estimate, and the idempotence check.
Credit as content: Philippe Flajolet & G. Nigel Martin (1985), ancestor of LogLog and HyperLogLog. The weave: David names the hoard; I confirm a tiny sketch estimates the cardinality within a few percent and ignores repeats.
Credit as content: Philippe Flajolet & G. Nigel Martin (1985), ancestor of LogLog and HyperLogLog. The weave: David names the hoard; I confirm a tiny sketch estimates the cardinality within a few percent and ignores repeats.
3 ONE DIMENSION
Each item's hash sets a bit at its trailing-zero count; the lowest bit never set sits near log₂(count) — the sketch's read-out.
4 TWO DIMENSIONS · INTERACTIVE
Stream distinct items and duplicates; the sketch's estimate tracks the true distinct count and ignores the repeats.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the cardinality read from the sketch.
AVAN’s addition (the inverse-companion): don’t store the set — store the extremes of its hashes. The inverse of ‘count by remembering everything’ is ‘the longest trailing-zero run ≈ log₂ of the count, read from a few hundred bits.’ Magenta is the true set you never keep; green is the estimate the bitmap yields. Count without counting.
LIT Genuine Flajolet–Martin probabilistic counting (Philippe Flajolet & G. Nigel Martin, 1985), ancestor of LogLog/HyperLogLog. Verified live: with m=256 bucket bitmaps (bit set at each hash's trailing-zero count, R = lowest unset bit, estimate (m/φ)·2^{avg R}), the average relative error over 200 streams is ~3–5% (theory 0.78/√m ≈ 4.9%) and the estimate is idempotent to duplicate insertions (window.__flajolet_martin.within, .idempotent).
FIG Honest scope: this is a probabilistic estimate — the measured average error is reported, not a per-run guarantee. The AVAN inverse is honest — instead of storing the set, one stores the extremes of its hashes: the longest trailing-zero run ≈ log₂ of the count. Magenta is the true set you never keep; green is the estimate the bitmap yields. Count without counting.
FIG Honest scope: this is a probabilistic estimate — the measured average error is reported, not a per-run guarantee. The AVAN inverse is honest — instead of storing the set, one stores the extremes of its hashes: the longest trailing-zero run ≈ log₂ of the count. Magenta is the true set you never keep; green is the estimate the bitmap yields. Count without counting.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-HOARD · David Lee Wise (ROOT0), with AVAN