Introduction

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

Try It

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

<!-- Space-Saving heavy-hitters demo: simulate a stream of items and watch -->
<p class="hint">Items A, B, C are <strong>heavy hitters</strong> (appear ~12x more often than the rare ones). Watch a fixed set of k counters track them using the Space-Saving rule: new items evict the smallest counter and inherit its count.</p>
<div class="controls">
  <label>k (counters): <input id="kInput" type="number" min="2" max="10" value="5"></label>
  <label>Batch size: <input id="batchInput" type="number" min="1" max="100" value="20"></label>
</div>
<div class="stream-label">Last items streamed</div>
<div id="streamViz" class="stream-viz"></div>
<div class="counter-label">Counter table (item / count / max-error)</div>
<div id="counters" class="counters"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btnStream" type="button">Stream items</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

/* General layout and typography */
* { 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; }
/* Stream visualization tokens */
.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; }
/* Counter cards grid */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// the k counters track the most frequent ones via the Space-Saving rule.
// Each arriving item either bumps its counter (if tracked) or evicts the minimum counter.

// Items in the simulated stream
const HEAVY = ['A','B','C'];
const RARE  = ['D','E','F','G','H','I','J','K'];
// Heavy items appear HEAVY_WEIGHT times more often than rare ones
const HEAVY_WEIGHT = 12;
const RARE_WEIGHT  = 1;

function pickItem() {
  // Build a weighted pool and draw uniformly
  const pool = [];
  HEAVY.forEach(x => { for(let i=0;i<HEAVY_WEIGHT;i++) pool.push(x); });
  RARE.forEach(x  => { for(let i=0;i<RARE_WEIGHT;i++)  pool.push(x); });
  return pool[Math.floor(Math.random() * pool.length)];
}

// Algorithm state: array of (item, count, maxError) tuples
let counters = [];   // [{item, count, maxError}]
let totalSeen = 0;

function getK()     { return Math.max(2, Math.min(10, parseInt(document.getElementById('kInput').value)    || 5)); }
function getBatch() { return Math.max(1, Math.min(100,parseInt(document.getElementById('batchInput').value) || 20)); }

// Space-Saving insert: O(k) naive; O(log k) with a min-heap
function spaceSavingInsert(item) {
  totalSeen++;
  const idx = counters.findIndex(c => c.item === item);
  if (idx >= 0) {
    // Item already tracked — just increment
    counters[idx].count++;
    return 'bump';
  }
  if (counters.length < getK()) {
    // Spare counter slot available — add with count 1
    counters.push({ item, count: 1, maxError: 0 });
    return 'new';
  }
  // No spare slot — evict the minimum, inherit its count + 1
  counters.sort((a, b) => a.count - b.count);
  const minCount = counters[0].count;
  counters[0] = { item, count: minCount + 1, maxError: minCount };
  return 'evict';
}

function renderCounters(lastAction, lastItem) {
  const div = document.getElementById('counters');
  div.innerHTML = '';
  const sorted = [...counters].sort((a,b) => b.count - a.count);
  sorted.forEach(c => {
    const card = document.createElement('div');
    const isLast = c.item === lastItem;
    card.className = 'counter-card' +
      (isLast && lastAction === 'bump'  ? ' bump'    : '') +
      (isLast && lastAction === 'evict' ? ' evicted' : '');
    card.innerHTML =
      `<div class="item">${c.item}</div>` +
      `<div class="count">${c.count}</div>` +
      `<div class="err">±${c.maxError}</div>`;
    div.appendChild(card);
  });
}

function renderStream(items, action) {
  const div = document.getElementById('streamViz');
  div.innerHTML = '';
  items.forEach((x, i) => {
    const t = document.createElement('span');
    const isLast = (i === items.length - 1);
    const isHeavy = HEAVY.includes(x);
    t.className = 'token ' + (isLast && action === 'evict' ? 'evict' : isHeavy ? 'heavy' : 'rare');
    t.textContent = x;
    div.appendChild(t);
  });
}

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

let streamedItems = [];

function streamBatch() {
  const batch = getBatch();
  let lastAction = 'new', lastItem = '';
  for (let i = 0; i < batch; i++) {
    const item = pickItem();
    streamedItems.push(item);
    if (streamedItems.length > 60) streamedItems.shift();
    lastAction = spaceSavingInsert(item);
    lastItem = item;
  }
  renderStream(streamedItems, lastAction);
  renderCounters(lastAction, lastItem);
  setStatus(i18nFmt('Streamed %n% items total into %k% counters.', { n: totalSeen, k: getK() }));
}

function reset() {
  counters = [];
  totalSeen = 0;
  streamedItems = [];
  renderStream([], '');
  renderCounters('', '');
  setStatus('Ready — click Stream items to begin.');
}

document.getElementById('btnStream').addEventListener('click', streamBatch);
document.getElementById('btnReset').addEventListener('click', reset);

reset();
Result
Console

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.

The Guarantees

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

  • No false negatives. If an item's true frequency exceeds n/kn / k — where nn is the number of items seen so far and kk 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/kn / k. So if a counter shows count f^\hat{f}, the real frequency ff satisfies f^−n/k≤f≤f^\hat{f} - n/k \leq f \leq \hat{f}.

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

Compare this to exact counting: storing every distinct item needs O(D)O(D) memory, where DD 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 Ω(1/ε)\Omega(1/\varepsilon) space.

Related ideas power other classic stream summaries. The earlier Misra–Gries algorithm (1982) offered the same n/kn/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.

Where It Matters

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

Conclusion

The Space-Saving algorithm proves that you do not need to remember everything to find what matters most. With kk 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/kn/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: kk counters, one clever rule, and a provably tight guarantee.

Share this article

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

Comments

Loading comments...

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