Why architecture matters here
Architecture matters here because the exact solution does not exist at scale and the obvious approximations are worse than they look. Sampling the stream and counting the sample under-counts exactly the items you care about least reliably. Hashing everything into a sketch like Count-Min gives you frequency estimates but not the identity of the top-k — a sketch can tell you how often a key you name appears, but it cannot by itself hand you the list of the most frequent keys, because it does not remember which keys it saw. Space-Saving is built specifically to produce that list, with counts and error bounds, in bounded memory.
The single-pass, bounded-memory property is the whole point. The stream is unbounded and possibly infinite; you may only touch each element once, and you have a fixed memory budget. Space-Saving fits exactly this model: k counters, one comparison-and-update per element, no second pass, no growth. Whether the stream has a thousand distinct keys or a billion, the memory is the same k slots. That is what makes it deployable in a router, a log pipeline, or a metrics aggregator where you cannot pause to sort and cannot afford per-key state.
The guarantee is what separates Space-Saving from a heuristic. Every recorded count is an over-estimate by at most the stored error, so the true count is bracketed in a known interval. This yields two strong statements. First, any item whose recorded count minus its error still exceeds the count of the item just below the reporting threshold is a guaranteed heavy hitter — it is definitely in the top-k, not a false positive. Second, the sum of all counts equals the number of items processed, so the counts are a genuine partition of the stream, not free-floating estimates. Those properties let you make claims about the top-k with confidence, not just report numbers and hope.
The behavior degrades gracefully with the stream's skew, which is exactly the parameter that matters in practice. Real frequency distributions are heavily skewed — a small number of items dominate, the rest form a long thin tail. When the distribution is skewed, the true heavy hitters have counts far above the min-count floor, so they are never evicted and their error bounds are tiny relative to their counts. When the distribution is flat — every item roughly equally frequent — there are no real heavy hitters to find, and Space-Saving's answers become appropriately uncertain, which is honest rather than misleading.
Finally, the memory-accuracy trade is a single clean dial. More counters (larger k) means a lower min-count floor, which means smaller error bounds and more items that can be guaranteed heavy hitters; fewer counters means a higher floor and looser bounds. There is no separate hash-collision knob, no independent depth-versus-width choice as in a sketch — just k. That simplicity makes Space-Saving easy to size: pick k from how many top items you need to report and how tight you need the bounds, and the behavior follows directly.
The architecture: every piece explained
Start with the counter table. Space-Saving maintains exactly k monitored keys, each with a count and an error. When a stream item x arrives, the first question is whether x is already monitored — whether it is one of the k keys currently in the table. This membership test has to be fast, so the table is backed by a hash map from key to its counter, giving constant-time lookup.
If x is monitored, the update is trivial: increment its count by one and leave its error unchanged. This is the common case for a true heavy hitter, which lives in the table permanently and just accumulates. If x is not monitored and there is still a free slot (the table has not yet reached k entries), x simply takes a new slot with count one and error zero. The interesting case is the third: x is not monitored and the table is full.
In that full-table case Space-Saving executes its signature move. It finds the entry m with the minimum count in the table, evicts m entirely, and inserts x into m's slot. The new key x gets count equal to m's count plus one — it inherits the floor and adds its own single occurrence — and it records error equal to m's old count, because that is the maximum amount by which x's new count might overstate x's true frequency (x might genuinely have appeared only once, in which case everything above one is inherited overestimate). This is the whole algorithm: increment if present, else evict the minimum and inherit-plus-one.
The efficiency of that move depends entirely on finding the minimum quickly, and that is what the Stream-Summary structure provides. Naively scanning all k counters for the minimum on every miss would cost O(k) per item — too slow for a high-rate stream. The Stream-Summary keeps the counters grouped by their count value in a structure (buckets of equal-count keys linked in count order) that exposes the current minimum in O(1) and supports incrementing a key and moving it to the next bucket in O(1) as well. With it, every stream item — hit or miss — is processed in constant time.
The guarantee box states the invariant that makes the output meaningful: for every monitored key, its true count lies in the interval from (recorded count minus error) up to (recorded count). The lower end is guaranteed because the key really did occur at least that many times since it was inserted; the upper end because the count can only over-estimate by the inherited floor. The ops strip names the health signals: how k compares to the stream's skew, the current min-count floor (which sets the eviction threshold and the error scale), the eviction rate (how much churn the table sees), how many keys clear the guaranteed-hitter bar, and the typical error width relative to counts.
End-to-end flow
Walk a short stream through a table of k=3 counters. The stream begins A, B, C. Each is new and there is room, so the table fills: A has count 1, B has count 1, C has count 1, all with error 0. The table is now full at three entries.
Next comes A again. A is monitored, so this is a simple hit: A's count rises to 2, error stays 0. Then B arrives, another hit: B goes to count 2, error 0. The table is A=2, B=2, C=1. Now a new key D arrives. D is not monitored and the table is full, so Space-Saving finds the minimum-count entry — C, at count 1 — evicts C, and inserts D with count equal to C's count plus one, so D=2, and error equal to C's old count, so D carries error 1. That error is the algorithm being honest: D might truly have appeared just once, and the extra 1 is inherited from C's floor.
The stream continues and D turns out to be genuinely frequent: D, D, D arrive as hits, driving D's count to 5 while its error stays pinned at 1. Now interpret D's counter with the guarantee: D's true count lies between (5 minus 1) and 5 — that is, between 4 and 5. Even though the count was seeded with an inherited overestimate, the interval is tight, and the lower bound of 4 already tells you D is a substantial hitter. Meanwhile A and B, the other true heavies, sit with exact counts and zero error because they were never evicted.
Contrast that with what happens to the tail. Rare keys like C, and any other one-off keys that arrive after the table is full, get inserted at the current min-count floor, briefly occupy a slot, and are evicted again the next time an even newer rare key shows up. They churn through the table without ever accumulating, and Space-Saving never claims they are heavy hitters — their counts hover at the floor with errors nearly as large as the counts, so the guarantee interval for them is wide and uninformative. That is precisely correct: the algorithm concentrates its certainty on the items that matter and is candidly uncertain about the ones that do not.
Step back and see the shape of the result. After processing the whole stream in one pass with three counters, the table holds the genuine heavy hitters (A, B, D) with tight guaranteed intervals, and the tail has been correctly excluded. The min-count floor rose as the stream progressed, automatically raising the bar a key must clear to stay monitored. No key was ever undercounted. The memory never grew beyond three slots. And every reported count came with an explicit error, so a consumer could distinguish a guaranteed hitter from a marginal one. All of that emerged from the single rule: increment if present, else evict the minimum and inherit its count plus one.