Space-Saving Heavy Hitters

Imagine a router that sees a billion packets per second, or a search engine tallying every query typed by every user worldwide. You want to know: which items appear most often? Storing every item is impossible — the stream never ends and memory is finite.

This is the heavy-hitters problem: find every item whose frequency exceeds a fraction $\varepsilon$ of the total stream length, using only a small, fixed amount of memory — far less than the number of distinct items in the stream.

The elegant answer is the Space-Saving algorithm (Metwally, Agrawal, and El Abbadi, 2005). It keeps exactly $k$ counters. When a new item arrives and already has a counter, that counter is incremented. When a new item has no counter, it evicts the counter with the smallest count and takes its slot — inheriting that count plus one. That tiny rule is enough to guarantee that every true heavy hitter is always tracked.

This article is about how a handful of counters can outrun a trillion-item flood — and why the algorithm's guarantees are surprisingly tight.

Click Stream items to send a torrent of items through a fixed set of $k = 5$ counters. Popular items (A, B, C) appear far more often than rare ones. Watch which labels survive eviction and which get replaced.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label>{{label_k}} <input id="kInput" type="number" min="2" max="10" value="5"></label>
  <label>{{label_batch}} <input id="batchInput" type="number" min="1" max="100" value="20"></label>
</div>
<div class="stream-label">{{label_stream}}</div>
<div id="streamViz" class="stream-viz"></div>
<div class="counter-label">{{label_counters}}</div>
<div id="counters" class="counters"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btnStream" type="button">{{btn_stream}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.controls { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .6rem; align-items: center; }
.controls label { font-size: .85rem; display: flex; align-items: center; gap: .3rem; }
.controls input { width: 52px; padding: .2rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; font-size: .85rem; }
.stream-label, .counter-label { font-size: .78rem; font-weight: 600; color: #666; letter-spacing: .04em; text-transform: uppercase; margin-bottom: .25rem; }
/* {{c_stream_viz}} */
.stream-viz { display: flex; flex-wrap: wrap; gap: 3px; min-height: 28px; margin-bottom: .5rem; }
.token { display: inline-flex; align-items: center; justify-content: center;
         width: 26px; height: 26px; border-radius: 5px; font: 700 12px ui-monospace, monospace;
         transition: opacity .3s; }
.token.heavy { background: #1d3557; color: #fff; }
.token.rare   { background: #c9ccd1; color: #444; }
.token.evict  { background: #e63946; color: #fff; opacity: .7; }
/* {{c_counters_bar}} */
.counters { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: .5rem; }
.counter-card { border: 1.5px solid #cdd9e3; border-radius: 8px; padding: .35rem .55rem;
                min-width: 54px; text-align: center; background: #e8eef3; transition: background .2s, border-color .2s; }
.counter-card.bump { background: #d0f0e0; border-color: #0a7d33; }
.counter-card.evicted { background: #fde8ea; border-color: #e63946; }
.counter-card .item { font: 700 16px ui-monospace, monospace; color: #1d3557; }
.counter-card .count { font-size: .75rem; color: #555; }
.counter-card .err { font-size: .65rem; color: #888; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin-bottom: .4rem; color: #1d3557; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice how A, B, and C almost always end up in the top counters even though you never stored the full stream. Each time a new item has no slot, it evicts the minimum counter — but the true heavy hitters keep winning their slots back because they arrive so frequently.

Space-Saving's power comes from a pair of proven guarantees:

• No false negatives. If an item's true frequency exceeds $n / k$ — where $n$ is the number of items seen so far and $k$ is the counter budget — that item is guaranteed to hold a counter. True heavy hitters are never silently dropped.
• Bounded overcount. Every counter's reported frequency overestimates the true frequency by at most $n / k$. So if a counter shows count $\hat{f}$, the real frequency $f$ satisfies $\hat{f} - n/k \leq f \leq \hat{f}$.

These two facts together mean: set $k = 1/\varepsilon$ and every item whose true frequency exceeds $\varepsilon \cdot n$ is found, with error at most $\varepsilon \cdot n$. The algorithm uses $O(k)$ space — just $k$ (item, count) pairs — and processes each element in $O(\log k)$ time using a sorted structure (or $O(1)$ amortized with a min-heap).

Compare this to exact counting: storing every distinct item needs $O(D)$ memory, where $D$ can be the entire vocabulary size. The Space-Saving trade-off — a tiny, tunable overcount in exchange for a fixed memory footprint — is essentially optimal for streaming. It matches the lower bound: any one-pass streaming algorithm for heavy hitters must use $\Omega(1/\varepsilon)$ space.

Related ideas power other classic stream summaries. The earlier Misra–Gries algorithm (1982) offered the same $n/k$ error bound but was designed for the majority-element variant. Counting with hash sketches trades a different accuracy/memory knob. Space-Saving unifies and refines these into a single, elegant structure.

"Which items appear most often in this enormous stream?" is one of the most universal questions in data engineering, and Space-Saving answers it everywhere:

• Network traffic analysis: routers run Space-Saving to detect elephant flows — the handful of connections that consume most of the bandwidth — without storing per-flow state for millions of flows simultaneously.
• Trending search queries: search engines maintain a rolling window of queries; Space-Saving surfaces the trending ones in real time without storing every query ever typed.
• Database query optimization: query engines use heavy-hitter sketches to estimate which column values are most common, allowing the SQL optimizer to choose smarter join orders and index strategies.
• Ad fraud detection: advertising platforms watch for IP addresses or device IDs that appear with suspiciously high frequency — classic heavy hitter detection at billions of events per hour.
• Cache eviction policies: knowing which keys are heavy hitters lets a cache pre-warm or prioritize its most valuable entries.

The common thread is the same constraint: the stream is too large to store, time is too short to make multiple passes, yet you need the most frequent items with provable accuracy. Space-Saving delivers all three.

The Space-Saving algorithm proves that you do not need to remember everything to find what matters most. With $k$ counters, one pass through the stream, and a single eviction rule, it guarantees that every true heavy hitter is tracked — and that no counter's estimate is off by more than $n/k$.

That is the deeper lesson: the right data structure does not shrink the stream — it extracts only the signal that survives. Heavy hitters are not found by exhaustive memory; they are found because they keep winning their slots back. Next time you wonder how a search engine knows what is trending right now, or how a router flags a flood in milliseconds, remember: $k$ counters, one clever rule, and a provably tight guarantee.