Introduction

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 ⌊n/k⌋\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)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.

Try It

Choose a number of counters kk 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.

<!-- Misra-Gries demo layout -->
<div class="controls">
  <label>Counters k = <input id="k-input" type="number" min="2" max="8" value="4"></label>
  <label>Stream (space-separated items): <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">Stream</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="stream-row" id="stream-row"></div>
<div class="section-label">Active counters</div>
<div id="counters-area" class="counters-area"></div>
<div id="status" class="status"></div>
<div id="summary" class="summary" hidden></div>

/* Misra-Gries demo styles */
* { 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; }

// Misra-Gries summary: stream items one by one through k-1 counters.
// Guarantee: any item with frequency > n/k survives in the final summary.
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

let tokens = [], k = 4, pos = 0, counters = {}, cancelRounds = 0, running = false, stepTimer = null;

function parseStream() {
  return document.getElementById('stream-input').value.trim().split(/\s+/).filter(Boolean);
}

function readK() {
  const v = parseInt(document.getElementById('k-input').value, 10);
  return (isNaN(v) || v < 2) ? 2 : Math.min(v, 8);
}

function reset() {
  clearTimeout(stepTimer);
  running = false;
  tokens = parseStream();
  k = readK();
  pos = 0;
  counters = {};
  cancelRounds = 0;
  renderStream();
  renderCounters();
  setStatus('Ready — press Stream or Step.', 'info');
  document.getElementById('summary').hidden = true;
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-stream').disabled = false;
}

function renderStream() {
  const row = document.getElementById('stream-row');
  row.innerHTML = '';
  tokens.forEach((t, i) => {
    const d = document.createElement('div');
    d.className = 'token' + (i === pos ? ' current' : i < pos ? ' done' : '');
    d.textContent = t;
    row.appendChild(d);
  });
}

function renderCounters() {
  const area = document.getElementById('counters-area');
  area.innerHTML = '';
  const entries = Object.entries(counters).sort((a, b) => b[1] - a[1]);
  if (entries.length === 0) {
    const ph = document.createElement('span');
    ph.style.cssText = 'color:#aaa;font-size:.85rem;align-self:center';
    ph.textContent = '(no counters yet)';
    area.appendChild(ph);
    return;
  }
  entries.forEach(([item, cnt]) => {
    const d = document.createElement('div');
    d.className = 'counter';
    d.innerHTML = '<span class="c-item">' + item + '</span><span class="c-count">' + cnt + '</span>';
    area.appendChild(d);
  });
}

function setStatus(msg, cls) {
  const s = document.getElementById('status');
  s.textContent = msg;
  s.className = 'status ' + cls;
}

// Process one item from the stream.
function step() {
  if (pos >= tokens.length) {
    finishSummary();
    return;
  }
  const item = tokens[pos];
  if (counters[item] !== undefined) {
    // Item already tracked — increment its counter.
    counters[item]++;
    setStatus(i18nFmt('Incremented counter for ’%item%’.', { item }), 'info');
  } else if (Object.keys(counters).length < k - 1) {
    // Free slot available — start a new counter.
    counters[item] = 1;
    setStatus(i18nFmt('New counter started for ’%item%’.', { item }), 'info');
  } else {
    // All slots full — cancellation round.
    cancelRounds++;
    for (const key of Object.keys(counters)) {
      counters[key]--;
      if (counters[key] <= 0) delete counters[key];
    }
    // After cancellation the triggering item is not inserted — it is subsumed.
    setStatus(i18nFmt('Cancellation round %cancelRounds% — decremented all counters (item: ’%item%’).', { item, cancelRounds }), 'cancel');
  }
  // Advance to the next stream position.
  const oldPos = pos;
  pos++;
  renderCounters();
  // Update token highlights in the stream row.
  const row = document.getElementById('stream-row');
  const tokenEls = row.querySelectorAll('.token');
  if (tokenEls[oldPos]) {
    tokenEls[oldPos].className = 'token done';
  }
  if (tokenEls[pos]) {
    tokenEls[pos].className = 'token current';
  }
  if (pos >= tokens.length) {
    finishSummary();
  }
}

function finishSummary() {
  running = false;
  document.getElementById('btn-step').disabled = true;
  document.getElementById('btn-stream').disabled = true;
  const n = tokens.length;
  const threshold = Math.floor(n / k);
  const entries = Object.entries(counters).sort((a, b) => b[1] - a[1]);
  const summaryEl = document.getElementById('summary');
  if (entries.length === 0) {
    summaryEl.innerHTML = '<strong>No survivors — every item was cancelled out.</strong>';
  } else {
    const rows = entries.map(([item, cnt]) =>
      '<span class="c-item" style="display:inline-block;min-width:2em;font-weight:700">' + item + '</span> &rarr; ' + i18nFmt('reported count %cnt%', { cnt })
    ).join('<br>');
    summaryEl.innerHTML =
      '<strong>Final summary (candidates):</strong><br>' + rows +
      '<br><small>' + i18nFmt('Stream length n = %n%, k = %k%. Items with true frequency > %threshold% are guaranteed to appear. Cancellation rounds: %cancelRounds%.', { n, k, threshold, cancelRounds }) + '</small>';
  }
  summaryEl.hidden = false;
  setStatus('Done — see the final summary below.', 'done-msg');
}

function streamAll() {
  if (running) return;
  running = true;
  function tick() {
    if (!running || pos >= tokens.length) { running = false; return; }
    step();
    stepTimer = setTimeout(tick, 350);
  }
  tick();
}

document.getElementById('btn-stream').addEventListener('click', streamAll);
document.getElementById('btn-step').addEventListener('click', () => { running = false; step(); });
document.getElementById('btn-reset').addEventListener('click', reset);

reset();
Result
Console

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/kn/k times will be in the final summary. The demo also shows how many cancellation rounds occurred, which is bounded by ⌊n/(k−1)⌋\lfloor n/(k-1) \rfloor.

The Real Complexity

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

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

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

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

f−nk≤f^≤ff - \frac{n}{k} \leq \hat{f} \leq f

Why the bound is tight: construct a stream of k−1k - 1 distinct items, each appearing exactly ⌊n/k⌋\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−1k - 1 tracked items. The heavy hitter survives because it appears just often enough. This worst case shows the bound n/kn/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.

Where It Matters

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/2n/2 times) is the special case k=2k = 2 of Misra-Gries. And the count-min sketch generalizes the idea to probabilistic point queries over the full frequency distribution.

Conclusion

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−1k - 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/misra-gries/Content licensed under CC BY-NC 4.0.