The Misra-Gries Summary

Imagine you are watching a billion website requests go by, one per millisecond. You cannot store them all — there is no buffer big enough. But you need to know: which items appear more than 1% of the time? Those are the heavy hitters, and missing even one could mean missing a denial-of-service attack or the next viral trend.

In 1982, Jayadev Misra and David Gries published a deceptively simple answer. Using only k counters — a data structure that fits in a few kilobytes — their algorithm reads the stream once, front to back, and guarantees that every item appearing more than $\lfloor n/k \rfloor$ times is still tracked at the end. Nothing that matters slips through.

The trick is a single, brutal operation: whenever the counters fill up, subtract 1 from all of them and discard any that hit zero. It looks destructive. But the math shows that this subtraction can only happen at most $n/(k-1)$ times, and any true heavy hitter is too frequent to be eliminated entirely.

This is streaming algorithm design at its best: a worst-case guarantee achieved with constant working memory, in a single pass, with no randomness needed.

Choose a number of counters $k$ and press Stream. Items flow in one at a time. If an item already has a counter, its count increments. If there is a free slot, a new counter starts. Otherwise every counter drops by 1 and those that reach zero are discarded — the cancellation step.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_k}} <input id="k-input" type="number" min="2" max="8" value="4"></label>
  <label>{{lbl_stream}} <input id="stream-input" type="text" value="A A A B B B C C D E A B F G A B C"></label>
</div>
<div class="btns">
  <button id="btn-stream" type="button">{{btn_stream}}</button>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="stream-row" id="stream-row"></div>
<div class="section-label">{{lbl_counters}}</div>
<div id="counters-area" class="counters-area"></div>
<div id="status" class="status"></div>
<div id="summary" class="summary" hidden></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem 1rem; margin-bottom: .5rem; align-items: center; }
.controls label { display: flex; align-items: center; gap: .4rem; font-weight: 600; font-size: .85rem; }
input[type=number] { width: 52px; padding: .25rem .4rem; border: 1px solid #aaa; border-radius: 6px; font-size: .9rem; }
input[type=text] { width: 260px; padding: .25rem .5rem; border: 1px solid #aaa; border-radius: 6px; font-size: .85rem; font-family: ui-monospace, monospace; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.stream-row { display: flex; flex-wrap: wrap; gap: 4px; min-height: 36px; margin-bottom: .4rem; }
.token { width: 28px; height: 28px; display: flex; align-items: center; justify-content: center;
         font: 700 13px ui-monospace, monospace; border-radius: 5px; border: 1px solid #cdd9e3; background: #e8eef3; transition: background .2s, transform .2s; }
.token.current { background: #f4a261; border-color: #d4763a; color: #fff; transform: scale(1.2); }
.token.done { background: #c5e3c5; border-color: #6aa96a; color: #1a4d1a; }
.token.cancelled { background: #f0d0d0; border-color: #c08080; color: #7a2020; }
.section-label { font-size: .75rem; font-weight: 700; color: #666; text-transform: uppercase; letter-spacing: .06em; margin-bottom: .3rem; }
.counters-area { display: flex; flex-wrap: wrap; gap: 6px; min-height: 52px; margin-bottom: .5rem; }
.counter { display: flex; flex-direction: column; align-items: center; padding: .3rem .6rem;
           border-radius: 8px; border: 2px solid #1d3557; background: #e8eef3; min-width: 44px;
           transition: background .25s, transform .25s; }
.counter .c-item { font: 700 15px ui-monospace, monospace; color: #1d3557; }
.counter .c-count { font: 600 12px system-ui; color: #555; }
.counter.bump { background: #cfe8cf; border-color: #3a8a3a; transform: scale(1.15); }
.counter.new-slot { background: #d8e8f8; border-color: #3a5a8a; }
.counter.dying { background: #f8d8d8; border-color: #c04040; opacity: .5; transform: scale(.85); }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin: .2rem 0; }
.status.info { color: #1d3557; }
.status.cancel { color: #c03030; }
.status.done-msg { color: #1a7030; }
.summary { margin-top: .5rem; padding: .5rem .7rem; background: #f0f8f0; border: 1px solid #8aba8a; border-radius: 8px; font-size: .85rem; }
.summary strong { color: #1a5030; }

// Code not found

Watch how frequent items (A, B, C in the default stream) survive the cancellations while rare ones vanish. The algorithm never promises exact counts — it promises that any item appearing more than $n/k$ times will be in the final summary. The demo also shows how many cancellation rounds occurred, which is bounded by $\lfloor n/(k-1) \rfloor$.

The Misra-Gries summary was proven correct — and tight — in the original 1982 paper.

Space: exactly $k - 1$ counters suffice to guarantee that no item appearing more than $n/k$ times is missed. Each counter stores one item label and one integer, so the total space is $O(k)$, independent of $n$ or the alphabet size.

Time: each stream element is processed in $O(\log k)$ time (a hash-map lookup), so the total time is $O(n \log k)$ — effectively linear.

The guarantee: after one pass, every item with true frequency $f > n/k$ appears in the summary. The reported count may be lower than the true count by at most $n/k$, but it is never higher. Formally, if $\hat{f}$ is the reported count and $f$ is the true count:

$$f - \frac{n}{k} \leq \hat{f} \leq f$$

Why the bound is tight: construct a stream of $k - 1$ distinct items, each appearing exactly $\lfloor n/k \rfloor$ times, then add one more item for the remainder. Every cancellation event eliminates exactly one copy of each of the $k - 1$ tracked items. The heavy hitter survives because it appears just often enough. This worst case shows the bound $n/k$ cannot be improved without more counters.

Compared to the count-min sketch, Misra-Gries uses deterministic space and gives a one-sided error: it never overcounts. The sketch trades that determinism for the ability to handle multiple queries and adversarial streams.

Any system that faces a firehose of data and needs to rank the dominant items turns to algorithms in the Misra-Gries family:

• Network traffic monitoring: routers run heavy-hitter detection to spot DDoS attack sources, elephant flows, and top-k destinations in real time — with counters measured in kilobytes, not gigabytes.
• Database query optimization: systems like PostgreSQL and Redshift maintain frequency sketches over column values to build accurate histograms for the query planner without scanning the full table on every schema change.
• Stream processing engines: Apache Flink and Spark Streaming use Misra-Gries variants to report trending items, detect anomalies, and power real-time dashboards over infinite event logs.
• Cache eviction policies: knowing which items are requested most frequently lets a cache pre-warm the right keys and avoid thrashing on adversarial access patterns.
• A/B testing and analytics: counting which experiment variant dominates traffic is a streaming frequent-item problem at scale.

The algorithm's influence also flows through later work. The Boyer-Moore majority vote algorithm (for finding an item that appears more than $n/2$ times) is the special case $k = 2$ of Misra-Gries. And the count-min sketch generalizes the idea to probabilistic point queries over the full frequency distribution.

The Misra-Gries summary is a masterclass in algorithm design under constraints. You cannot store the stream, you cannot rewind it, and you must answer a meaningful question at the end. The solution: keep only $k - 1$ counters and cancel them in bulk whenever they fill up. The math ensures that anything important is too frequent to disappear entirely.

Published in 1982, the algorithm predates the term "streaming algorithm" by nearly two decades — yet it satisfies every modern requirement: one pass, sublinear space, deterministic guarantees, and no randomness. It is the Boyer-Moore majority vote generalized, and the conceptual parent of every frequency sketch in use today.

The next time your database planner knows which column values dominate, or your router flags a flood attack before it overwhelms the link, there is a good chance a descendant of Misra-Gries is quietly counting behind the scenes.