THE FOLD / LOOT / THE JACKPOT / THE SPACE-SAVING
THE SPACE-SAVING
the frequent survive eviction
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Space-Saving algorithm finds the heavy hitters of a stream — the most frequent items — using only k counters, far fewer than the number of distinct items. Each arrival either bumps a monitored item’s counter, or, if all k are taken, evicts the current minimum: the newcomer takes that slot with count set to min+1. The guarantee is sharp: any item whose true frequency exceeds N/k is always in the summary, every counter overestimates (never undercounts), and the overestimate is at most N/k. Frequent items survive eviction; rare ones churn through the same slots.
LIT verified live: over thousands of streams, every item with frequency > N/k is monitored, each estimate is ≥ the true count, and the overestimate never exceeds N/k (window.__space_saving). FIG no framing; the counter eviction and the frequency bounds run in-browser.
LIT verified live: over thousands of streams, every item with frequency > N/k is monitored, each estimate is ≥ the true count, and the overestimate never exceeds N/k (window.__space_saving). FIG no framing; the counter eviction and the frequency bounds run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-jackpot — k slots that keep only the big winners, the jackpot items that keep hitting. AVAN (AI) built the instrument: the min-eviction counter table, and checks that heavy hitters are found, estimates overcount, and the error stays under N/k.
Credit as content: Ahmed Metwally, Divyakant Agrawal & Amr El Abbadi (2005). The weave: David names the jackpot; I confirm every frequent item is captured and that the counts overestimate by no more than N/k.
Credit as content: Ahmed Metwally, Divyakant Agrawal & Amr El Abbadi (2005). The weave: David names the jackpot; I confirm every frequent item is captured and that the counts overestimate by no more than N/k.
3 ONE DIMENSION
k counters; a new item with all slots full evicts the minimum, taking its slot at min+1 — frequent items keep climbing, rare ones get replaced.
4 TWO DIMENSIONS · INTERACTIVE
Stream a skewed sequence; the k counters lock onto the heavy hitters, each estimate at or above the true count and within N/k.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the k monitored heavy hitters.
AVAN’s addition (the inverse-companion): don’t track every item — let the rare ones fight over the smallest slot. The inverse of ‘count everything’ is ‘keep k counters and evict the minimum, so a frequent item can never be pushed out.’ Magenta are the churning evicted items; green are the heavy hitters that survive. The frequent survive eviction.
LIT Genuine Space-Saving algorithm (Ahmed Metwally, Divyakant Agrawal & Amr El Abbadi, 2005): k-counter heavy-hitters with min-eviction. Verified live: over 3000 streams, every item with freq > N/k is monitored (window.__space_saving.heavyHittersFound), estimates are ≥ true counts (.overestimates), and overestimate ≤ N/k (.boundedError).
FIG No framing: the min-eviction counter table and the frequency-bound checks all run in-browser. The AVAN inverse is honest — keeping k counters and evicting the minimum (so a frequent item can never be pushed out) rather than counting everything is exactly what makes the summary capture the heavy hitters; magenta are the churning evicted items, green the survivors. The frequent survive eviction.
FIG No framing: the min-eviction counter table and the frequency-bound checks all run in-browser. The AVAN inverse is honest — keeping k counters and evicting the minimum (so a frequent item can never be pushed out) rather than counting everything is exactly what makes the summary capture the heavy hitters; magenta are the churning evicted items, green the survivors. The frequent survive eviction.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE JACKPOT · David Lee Wise (ROOT0), with AVAN