Large streaming systems often need to answer a simple question:

How many times did this item appear?

For a small stream, a hash map is enough. For a huge stream, that hash map can become too large because it has to store every distinct key.

A Count-Min Sketch gives approximate counts using fixed memory. Each item updates a few counters in a table. Later, the sketch reads those counters to estimate the item’s count.

It is useful when the stream is too big, too fast, or spread across too many machines to count exactly. It is also easy to merge across shards by adding matching counters together.

The trade-off is accuracy. With normal non-negative updates, a Count-Min Sketch does not count too low, but hash collisions can make it count too high. It can estimate the count of an item you ask about, but it cannot list all items by itself.

This chapter explains what Count-Min Sketch stores, why errors happen, how merging works, how to find heavy hitters, and where it is useful in real systems.

The exact approach is a hash map:

This is exact and simple. The problem is that every new key costs more than one counter. The system also stores the key itself, hash-table bookkeeping, memory-allocation overhead, and any replication or checkpoint data.

In a stream with millions or billions of distinct keys, exact maps become expensive. They are also hard to merge if every shard has a large local map.

Count-Min Sketch is useful when:

It is a poor fit when you need exact counts, a list of all items, or accurate counts for rare items.