THE FOLD / LOOT / THE DROP / THE MISRA-GRIES
THE MISRA-GRIES
frequent items from a stream in k-1 counters
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Misra–Gries algorithm finds the frequent items in a stream using only k−1 counters — far fewer than the number of distinct items. For each element: if it has a counter, increment; else if a counter is free, start one; else decrement every counter (dropping any that hit zero). When the stream ends, every item whose true frequency exceeds n/k is guaranteed to still have a counter.
It is the streaming heavy-hitters primitive, and a direct generalisation of the Boyer–Moore majority vote.
LIT verified live: over 500 random streams every item with frequency > n/k survives in the summary, every reported count is ≤ the true count, and the summary never exceeds k−1 entries (window.__misragries). FIG no framing; the guarantee holds exactly.
It is the streaming heavy-hitters primitive, and a direct generalisation of the Boyer–Moore majority vote.
LIT verified live: over 500 random streams every item with frequency > n/k survives in the summary, every reported count is ≤ the true count, and the summary never exceeds k−1 entries (window.__misragries). FIG no framing; the guarantee holds exactly.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-drop — which loot drops most often, tracked with only a handful of slots as the drops stream past. Misra–Gries is that cheap frequency tracker. AVAN (AI) built the instrument: the k−1 counters, the decrement-all rule, the heavy-hitter guarantee check.
Credit as content: Jayadev Misra & David Gries (1982), generalising Boyer–Moore majority. The weave: David names the drop; I keep a few counters, let collisions cancel the rare items, and confirm every frequent item survives.
Credit as content: Jayadev Misra & David Gries (1982), generalising Boyer–Moore majority. The weave: David names the drop; I keep a few counters, let collisions cancel the rare items, and confirm every frequent item survives.
3 ONE DIMENSION
The stream flows past k−1 counters: a match increments, a free slot opens a new counter, and an overflow decrements them all at once — rare items cancel out, frequent ones persist.
4 TWO DIMENSIONS · INTERACTIVE
A stream over a small alphabet with k counters. The Misra–Gries summary is shown against the true frequencies; every true heavy hitter (> n/k) is retained.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the surviving heavy hitters, held in a handful of counters.
AVAN’s addition (the inverse-companion): you find the frequent items without counting all of them. With k−1 counters and a decrement-all-on-overflow rule, every item above n/k survives while the rare ones cancel each other. The inverse of ‘keep a count per distinct item’ is ‘keep k−1 counters and let collisions erase the noise.’ Magenta is the exact per-item counts you never store; green is the heavy hitters guaranteed to remain. Bounded memory, and it keeps exactly what matters — the majority vote, generalised past two.
LIT Genuine Misra-Gries algorithm (Misra & Gries 1982). Verified live: over 500 random streams, every element with true frequency > n/k remains in the k-1-counter summary, every reported count <= the true count, and the summary size stays <= k-1 (window.__misragries.allHeavyPresent && .underestimates && .sizeBounded).
FIG No framing: the k-1 counters, the decrement-all rule, and the heavy-hitter/underestimate/size checks run in-browser and hold exactly. The AVAN inverse is honest — bounded counters with decrement-on-overflow let rare items cancel while every item above n/k survives, so you find the frequent items without counting all of them; magenta is the exact per-item counts never stored, green the surviving heavy hitters. Boyer-Moore majority generalized.
FIG No framing: the k-1 counters, the decrement-all rule, and the heavy-hitter/underestimate/size checks run in-browser and hold exactly. The AVAN inverse is honest — bounded counters with decrement-on-overflow let rare items cancel while every item above n/k survives, so you find the frequent items without counting all of them; magenta is the exact per-item counts never stored, green the surviving heavy hitters. Boyer-Moore majority generalized.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE DROP · David Lee Wise (ROOT0), with AVAN