THE FOLD / LOOT / THE VAULT / THE COUNT-MIN SKETCH
THE COUNT-MIN SKETCH
count a huge stream in a tiny fixed table
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Count-Min sketch estimates how often each item appears in a huge stream using a tiny fixed table — d rows × w columns of counters — far smaller than the number of distinct items. Each item is hashed into one counter per row and increments them; its estimate is the minimum of those d counters. Because collisions can only add to a counter, the estimate is never an underestimate, and taking the min squeezes out most of the collision noise.
LIT verified live: over an 8000-item stream drawn from a 400-symbol alphabet the sketch’s estimate is ≥ the true count for every distinct item — it never underestimates (window.__cms). FIG no framing; exact.
LIT verified live: over an 8000-item stream drawn from a 400-symbol alphabet the sketch’s estimate is ≥ the true count for every distinct item — it never underestimates (window.__cms). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-vault — the ledger that must tally a torrent of items in a fixed, tiny space. The Count-Min sketch is that thimble-sized tally. AVAN (AI) built the instrument: the d×w counter table, the per-row hashes, the min-estimate, and the never-underestimate check against an exact map.
Credit as content: Graham Cormode & S. Muthukrishnan (2005). The weave: David names the vault; I hash each item into one counter per row, read back the minimum, and confirm the estimate is never below the true count.
Credit as content: Graham Cormode & S. Muthukrishnan (2005). The weave: David names the vault; I hash each item into one counter per row, read back the minimum, and confirm the estimate is never below the true count.
3 ONE DIMENSION
Each item hashes to one cell per row and bumps it. To query, read the item’s cell in every row and take the smallest — collisions only inflate cells, so the minimum is the tightest (and never-too-low) estimate.
4 TWO DIMENSIONS · INTERACTIVE
A d×w sketch over a skewed stream; query any item to compare its min-estimate against the true count — always ≥, never below.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: frequencies tallied in a fixed tiny table.
AVAN’s addition (the inverse-companion): count a stream too big to store in a fixed small table by hashing each item into d rows and reading back the minimum — since collisions only add, the min never underestimates. The inverse of ‘keep an exact counter per distinct item’ is ‘keep d×w counters and take the min — a one-sided, bounded error.’ Magenta is the unbounded exact map you avoid storing; green is the fixed sketch. A torrent counted in a thimble.
LIT Genuine Count-Min sketch (Cormode & Muthukrishnan 2005). Verified live: over an 8000-item skewed stream drawn from a 400-symbol alphabet, the min-of-d-rows estimate is greater than or equal to the true count for every distinct item that appears — it never underestimates (window.__cms.neverUnderestimates).
FIG No framing: the d x w counter table, the per-row hashes, the min-estimate, and the never-underestimate check against an exact map run in-browser and hold. The AVAN inverse is honest — hashing each item into d rows and reading back the minimum counts a stream too big to store in a fixed small table, with a one-sided (never-under) bounded error since collisions only add; magenta is the unbounded exact map you avoid, green the fixed sketch. A torrent counted in a thimble.
FIG No framing: the d x w counter table, the per-row hashes, the min-estimate, and the never-underestimate check against an exact map run in-browser and hold. The AVAN inverse is honest — hashing each item into d rows and reading back the minimum counts a stream too big to store in a fixed small table, with a one-sided (never-under) bounded error since collisions only add; magenta is the unbounded exact map you avoid, green the fixed sketch. A torrent counted in a thimble.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN