Introduction

Imagine a firehose: billions of search queries an hour, packets racing through a router, clicks pouring into a server. The data arrives once, far faster than you could ever write it down, and then it is gone. A natural question keeps coming back: which items show up the most? The trending searches, the chatty IP addresses, the best-selling products.

The obvious method is to keep a counter for every distinct item. But on a stream with millions of unique values, that table won't fit in memory — and on a true torrent, it never will. You get one pass and a tiny notepad.

The surprise is that you don't need a counter per item. With just a handful of counters, you can guarantee that every truly frequent item survives. The trick is knowing what to throw away.

Stream the Counters

Below, items fly past one at a time and a fixed set of k counters tries to track the frequent ones. The rule (Misra-Gries) is simple: if the item already has a counter, bump it; if there's a free slot, claim it; otherwise decrement every counter by one, evicting any that hit zero. Press play and watch the popular items cling to their slots while the rare ones get knocked out.

<p class="hint">A stream of items flies past one at a time. Only <b>k = 4</b> counters are available. The Misra-Gries rule: if the item has a counter, bump it; if a slot is free, claim it; otherwise <b>decrement every counter</b> and drop any that hit zero. Watch the frequent items survive while the rare ones get evicted.</p>
<div class="stream">
  <span class="lbl">Next:</span>
  <span id="next" class="next">--</span>
  <span id="progress" class="progress"></span>
</div>
<div id="counters" class="counters"></div>
<div class="status" id="status">Press Step or Play to feed the stream.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="play" type="button">Play</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="truth" class="truth"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.stream { display: flex; align-items: center; gap: .5rem; margin: .3rem 0 .6rem; }
.lbl { font-weight: 600; color: #555; }
.next { font: 700 20px ui-monospace, monospace; background: #1d3557; color: #fff;
        border-radius: 8px; padding: .25rem .7rem; min-width: 2.4em; text-align: center; }
.progress { font-size: .85rem; color: #777; }
.counters { display: grid; grid-template-columns: repeat(4, 1fr); gap: 8px; margin: .4rem 0; }
.slot { border: 1px solid #cdd9e3; border-radius: 10px; padding: .55rem .4rem; text-align: center;
        background: #f3f6f9; transition: all .15s; }
.slot.empty { background: #eceef1; border-style: dashed; color: #aab2bb; }
.slot.hit { background: #d6f0dd; border-color: #66c187; }
.slot.evict { background: #fbe0e3; border-color: #e88; }
.slot .item { font: 700 18px ui-monospace, monospace; color: #1d3557; }
.slot.empty .item { color: #aab2bb; }
.slot .cnt { font-size: .85rem; color: #555; margin-top: .2rem; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #333; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }
.truth { font-size: .82rem; color: #666; margin-top: .7rem; line-height: 1.5; }
.truth b { color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Misra-Gries heavy hitters (Misra & Gries, 1982). With k counters, any item whose true frequency exceeds 1/(k+1) of the stream is guaranteed to hold a counter at the end. Each item is processed in O(1) and total memory is just k slots — one pass.
const K = 4;
// A stream where 'A' and 'B' are heavy hitters and C..H are rare noise.
const STREAM = ['A','B','C','A','B','D','A','E','B','A','F','B','A','G','B','A','H','B','A','B'];

let pos = 0;
let counters = {};      // item -> count (at most K live keys)
let lastTouched = null; // for highlight

function mg(item){
  if (item in counters) { counters[item]++; return 'hit'; }
  if (Object.keys(counters).length < K) { counters[item] = 1; return 'new'; }
  // table full and item absent: decrement all, drop zeros
  for (const key of Object.keys(counters)) {
    counters[key]--;
    if (counters[key] === 0) delete counters[key];
  }
  return 'decrement';
}

function trueCounts(upto){
  const t = {};
  for (let i = 0; i < upto; i++) t[STREAM[i]] = (t[STREAM[i]]||0) + 1;
  return t;
}

function render(action){
  document.getElementById('next').textContent = pos < STREAM.length ? STREAM[pos] : 'done';
  document.getElementById('progress').textContent = fmt('%pos% / %length% items seen', { pos: pos, length: STREAM.length });
  const wrap = document.getElementById('counters');
  wrap.innerHTML = '';
  const keys = Object.keys(counters);
  for (let i = 0; i < K; i++) {
    const d = document.createElement('div');
    const key = keys[i];
    if (key === undefined) { d.className = 'slot empty'; d.innerHTML = '<div class="item">--</div><div class="cnt">empty</div>'; }
    else {
      let cls = 'slot';
      if (action === 'hit' && key === lastTouched) cls += ' hit';
      if (action === 'new' && key === lastTouched) cls += ' hit';
      d.className = cls;
      d.innerHTML = fmt('<div class="item">%key%</div><div class="cnt">count %v%</div>', { key: key, v: counters[key] });
    }
    wrap.appendChild(d);
  }
  if (action === 'decrement') {
    wrap.querySelectorAll('.slot').forEach(s => { if (!s.classList.contains('empty')) s.classList.add('evict'); });
  }
}

function setStatus(t){ document.getElementById('status').textContent = t; }

function showTruth(){
  if (pos < STREAM.length) { document.getElementById('truth').innerHTML = ''; return; }
  const t = trueCounts(STREAM.length);
  const sorted = Object.entries(t).sort((a,b)=>b[1]-a[1]);
  const survivors = Object.keys(counters).sort((a,b)=>counters[b]-counters[a]);
  const trueTop = sorted.filter(([,c]) => c > STREAM.length/(K+1)).map(([k])=>k);
  document.getElementById('truth').innerHTML =
    fmt('Stream finished. True frequencies: %map%.<br>Survivors in the %K% counters: <b>%survivors%</b>. Every item above the %length%/(%K%%v%) = %v2% threshold ( (%trueTop%) survived — exactly as guaranteed.', { map: sorted.map(([k,c])=>k+'='+c).join(', '), K: K, survivors: survivors.join(', '), length: STREAM.length, v: 1, v2: (STREAM.length/(K+1)).toFixed(1), trueTop: trueTop.join(', ') });
}

function step(){
  if (pos >= STREAM.length) { setStatus('Stream finished.'); return false; }
  const item = STREAM[pos];
  const action = mg(item);
  lastTouched = item;
  pos++;
  const msg = {
    hit: fmt('Saw %item% — already tracked, bumped its counter.', { item: item }),
    new: fmt('Saw %item% — free slot available, claimed it.', { item: item }),
    decrement: fmt('Saw %item% — table full, decremented all counters (zeros evicted).', { item: item })
  }[action];
  setStatus(msg);
  render(action);
  showTruth();
  return pos < STREAM.length;
}

let timer = null;
function play(){
  if (timer) return;
  document.getElementById('play').disabled = true;
  timer = setInterval(() => { if (!step()) { clearInterval(timer); timer = null; document.getElementById('play').disabled = false; } }, 700);
}
function reset(){
  if (timer) { clearInterval(timer); timer = null; document.getElementById('play').disabled = false; }
  pos = 0; counters = {}; lastTouched = null;
  setStatus('Press Step or Play to feed the stream.');
  document.getElementById('truth').innerHTML = '';
  render(null);
}

document.getElementById('step').addEventListener('click', step);
document.getElementById('play').addEventListener('click', play);
document.getElementById('reset').addEventListener('click', reset);
render(null);
Result
Console

Notice the asymmetry. With only k counters you never use more than a sliver of memory, yet any item appearing more than a 1/(k+1) fraction of the stream is guaranteed to still hold a counter at the end. Rare items churn through and vanish; the heavy hitters are the ones left standing. The counts may be undercounts, but the frequent few cannot hide.

The Real Complexity

How hard is finding the frequent items, really?

  • Exact, one pass, is impossible cheaply. Deciding precisely which items cross a frequency threshold in a single pass provably requires memory linear in the number of distinct items — there is no way around storing essentially everything. This is a proven space lower bound, not a missing trick.
  • Approximation is easy and solved. The Misra-Gries algorithm (Jayadev Misra and David Gries, 1982) keeps just k counters and processes each item in O(1)O(1). Any item with frequency above 1/(k+1) of the stream is guaranteed to survive; reported counts undercount the truth by at most the number of items seen divided by (k+1).
  • One-sided error. The sketch never misses a true heavy hitter (no false negatives among items above the threshold), though a borderline item may slip through. A second cleanup pass, if you can afford it, removes the false positives.
  • Space-Saving (Metwally et al., 2005) is a closely related, often more accurate variant that keeps the same fixed-size table but tracks an overestimate per slot.

So the status is clear: exact heavy hitters in one pass is proven to need linear space, while the approximate version is solved — a fixed handful of counters, one pass, with a clean guarantee. It is a textbook example of trading a little accuracy for an enormous saving in memory, the same bargain behind Bloom filters.

Where It Matters

"Which items are most frequent?" is one of the most common questions asked of data that is too big to keep, and the heavy-hitters sketch answers it in a single sweep:

  • Trending topics and search: surfacing the most popular queries, hashtags or videos from a torrent of events without storing every one.
  • Network monitoring: routers find the "top talkers" and spot a DDoS flood — a few source addresses suddenly dominating — using only on-chip counters.
  • Databases and caches: query optimizers track the most frequent values to plan joins, and caches keep the hottest keys resident.
  • Telemetry and logs: the noisiest error code or the busiest endpoint, found live in a pipeline that can't pause to sort.

Learn how heavy hitters work and you've met the streaming mindset — one pass, fixed memory, a small approximation — the same engine behind Bloom filters and other sketches that tame data too large to hold. Knowing the frequent items is also a building block for recommendation systems.

Conclusion

Heavy hitters capture a recurring lesson of computer science: when the data is too big to keep, stop trying to be exact. A few counters and the simple discipline of decrement-when-full let truly frequent items rise to the top while everything rare melts away — all in one pass and a fixed pinch of memory.

The exact problem is provably expensive, but the approximate one, solved by Misra and Gries in 1982, is both cheap and reliable. The next time you see a "trending now" list or a router flagging a flood of traffic, remember the trick underneath: you can't write down the whole torrent, but you can always make room for whatever keeps showing up.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/heavy-hitters-streaming/Content licensed under CC BY-NC 4.0.