THE FOLD / LOOT / THE STASH / THE SKETCH
THE SKETCH
Count-Min — tiny memory, never undercounts
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Count-Min Sketch. A billion events fly past — IP packets, search queries, words — and you want to know how often each one appeared, but you cannot store a counter for every distinct item. The Count-Min Sketch (Cormode & Muthukrishnan, 2005) does it in a tiny fixed grid: d rows of w counters and d hash functions.
To add an item, hash it d ways and bump those d counters. To query its count, take the minimum of its d counters. Different items collide and share cells — so a counter can only be too high, never too low. And taking the minimum across independent hashes finds the least-polluted estimate: the sketch never underestimates, and its overestimate is provably bounded.
LIT verified live: over hundreds of random streams the sketch’s estimate is always ≥ the true count — a strictly one-sided error — with a small, bounded overestimate (window.__countmin.neverUnderestimates; max over reported). FIG no framing; the hash-and-increment, the min-query, and the never-underestimate guarantee are exact.
To add an item, hash it d ways and bump those d counters. To query its count, take the minimum of its d counters. Different items collide and share cells — so a counter can only be too high, never too low. And taking the minimum across independent hashes finds the least-polluted estimate: the sketch never underestimates, and its overestimate is provably bounded.
LIT verified live: over hundreds of random streams the sketch’s estimate is always ≥ the true count — a strictly one-sided error — with a small, bounded overestimate (window.__countmin.neverUnderestimates; max over reported). FIG no framing; the hash-and-increment, the min-query, and the never-underestimate guarantee are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE STASH, beside THE CUCKOO and THE FENWICK LADDER — the loot domain of storing things to find fast. The sketch is a stash that gives up exactness for a fixed, tiny footprint, and pays it back with a guarantee: never too low. AVAN (AI) built the instrument: the hash grid, the min-query, the one-sided-error check.
The weave: David names the seat (the compact stash); I make the collisions visible and the guarantee provable — one item’s d cells in 1D, the streaming counter grid in 2D, the counter surface in 3D. The sphere is the seam. Credit: Graham Cormode & S. Muthukrishnan (2005).
The weave: David names the seat (the compact stash); I make the collisions visible and the guarantee provable — one item’s d cells in 1D, the streaming counter grid in 2D, the counter surface in 3D. The sphere is the seam. Credit: Graham Cormode & S. Muthukrishnan (2005).
3 ONE DIMENSION
One item, hashed into d rows, bumps one counter in each. A query re-hashes it to the same d cells and takes the smallest — because collisions from other items can only push a counter up, the minimum is the closest thing to the truth, and never below it.
4 TWO DIMENSIONS · INTERACTIVE
Stream items into the d×w grid — a few frequent, many rare. Query one: its d cells light up and the minimum is the estimate. Compare it to the true count — equal or a touch high, never low. The heavy hitters stand out even when memory is tiny.
5 THREE DIMENSIONS + AVAN’S INVERSE
The counter grid as a turning surface — green heights are how full each cell is; heavy hitters push ridges up.
AVAN’s addition (the inverse-companion): the magenta cells are one item’s d probes, and the estimate is their minimum. An exact tally needs a slot per distinct item — memory that grows without bound. The sketch is the inverse bargain: fix the memory and let everything collide, sharing counters. That should ruin the count — except that with d independent hashes, at least one of an item’s cells is the least polluted, and the minimum finds it. Accuracy comes not from space but from redundancy: overlap freely, then trust the smallest witness. The green is the shared, colliding grid; the magenta is the handful of probes whose minimum is never a lie downward.
LIT Genuine Count-Min Sketch (Cormode & Muthukrishnan, 2005). Verified live: over 200 random streams the sketch's estimate is always >= the true count — a strictly one-sided error — with a small, bounded overestimate (window.__countmin.neverUnderestimates === true; max over reported). The hash-and-increment, the min-query, and the never-underestimate guarantee (collisions only inflate; the minimum finds the least-polluted cell) are exact.
FIG No metaphor is doing the work: the hashing, the min-query, and the one-sided-error guarantee are all real and checked. It trades exactness for fixed memory — the error is provably one-sided (never under) and bounded, which is exactly the sketch's contract.
FIG No metaphor is doing the work: the hashing, the min-query, and the one-sided-error guarantee are all real and checked. It trades exactness for fixed memory — the error is provably one-sided (never under) and bounded, which is exactly the sketch's contract.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN