Heavy Hitters

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.

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">{{hint}}</p>
<div class="stream">
  <span class="lbl">{{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">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="play" type="button">{{btn_play}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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)$. 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.

"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.

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.