You're tracking the top 100 URLs in a stream of 10 billion requests per day. You can't keep a counter for every unique URL — that's tens of millions of entries. But you also can't afford the false positives of a Count-Min Sketch when you need to actually report the top items, not just estimate their counts. The Space-Saving algorithm (Metwally, Agrawal, El Abbadi, 2005) solves this with a fixed-size table of exactly K counters, one pass, and O(1) updates.

How it works. Keep a table of K entries, each storing an item and a counter. For each incoming item:

• If it's already in the table, increment its counter.
• If the table has an empty slot, insert the item with count 1.
• If the table is full, find the entry with the smallest count, replace its item with the new one, and increment that counter by 1.

That third step is the clever bit. The evicted item's count becomes the error bound for the new item — we're saying "this new item has been seen at least once, but possibly as many times as the loser we just kicked out." A companion field error tracks that overestimate per entry.

The guarantee. With K counters over N total items, any item whose true frequency exceeds N/K is guaranteed to be in the table. The estimated count is always ≥ the true count, and the overestimate is bounded by the minimum counter value at eviction time. No false negatives for the heavy hitters — only bounded overestimates.

Rule of thumb: to reliably find the top K items, allocate roughly 10×K counters. Want the top 100? Use 1,000 slots. Memory: 1,000 × (URL + 2 ints) ≈ 50 KB. Compare that to a naive HashMap on 50 million unique URLs at ~100 bytes each: 5 GB. Four orders of magnitude smaller.

Real-world example. A CDN wants to identify the top 500 hottest cache objects across a shard handling 2M requests/sec so it can promote them to an in-memory tier. A HashMap grows unbounded and OOMs by midday. Count-Min Sketch tells you an object's approximate count but not which objects are hot — you'd still need a separate structure. Space-Saving with 5,000 slots (~250 KB) directly maintains the candidate set as the stream flows, updated in a single lock-free CAS per request.

The catch. Space-Saving finds heavy hitters relative to the whole stream. If you need per-time-window top-K, pair it with a sliding-window scheme or run parallel instances per window.