Top-K / Space-Saving

Tracks the approximate most frequent items ("heavy hitters") in a stream using only k counters, no matter how many distinct items appear. Complements Count-Min Sketch: CMS answers "how many times has X appeared", Top-K answers "what are the most frequent items".

How it works

The Space-Saving algorithm keeps exactly k counters, each holding an item, a count, and an error bound. On add(item):

  • If item already owns a counter, just increment it (an exact count for that item).
  • Otherwise, if a counter is still free, give it to item with count 1 and error 0.
  • Otherwise, all k counters are occupied by other items: evict whichever counter has the smallest count, and give it to item with count = min + 1 and error = min. The error records that the new item might secretly have appeared up to min times before it stole this counter.

This guarantees count - error ≤ trueCount ≤ count for every tracked item, and -- the key "space-saving" property -- any item whose true frequency exceeds N / k (N = total items seen) is mathematically guaranteed to be tracked, so k counters is enough to never lose a real heavy hitter, even though it can't perfectly rank the long tail.

Interactive demo

Counters used0 / 5
Total items seen0
Guaranteed heavy hitter—
SpaceO(k)
No counters yet. Add an item below.
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new TopK(k)Allocate k counters for tracking the approximate top-k items.O(k) space
add(item, amount?): TopKAddResultIncrement, insert, or evict-and-replace a counter for item.O(k) time
top(n?): TopKEntry[]Return up to n tracked entries sorted by count descending.O(k log k) time
estimate(item): TopKEntry | undefinedReturn the counter for item if it is currently tracked.O(1) time
clear(): voidReset all counters and totalCount.O(k) time

References

Original papers

Library implementations

Real-world use cases