Count-Min Sketch

A market-data handler sees millions of trade messages a second across tens of thousands of symbols, and wants a running count of trades per symbol without keeping a hash map entry for every symbol that ever appears — including ones traded once and never again. A count-min sketch gives approximate counts for every item in a stream using a small, fixed-size table, at the cost of counts that are sometimes too high but never too low.

How it works

Build a table with $d$ rows and $w$ columns of counters, all starting at zero, and $d$ independent hash functions, one per row, each mapping an item to a column.

To update an item's count by 1: for each row $r$, hash the item to a column and increment that counter.

To query an item's count: for each row, look up the counter at that item's hashed column, then take the smallest of the $d$ values found.

Every counter a hash function points to also gets incremented by other items that happen to hash to the same column — collisions only ever push counts up, never down. Taking the minimum across rows picks the row where this item was, by chance, least corrupted by collisions, which is why the estimate is only ever an overestimate.

Worked example

Suppose the true trade count for symbol AAPL is 50, but the sketch reports counters 58, 61, and 50 across its three rows for AAPL's hashed columns. The query returns $\min(58, 61, 50) = 50$ — here the third row happened to have no collisions, so the estimate is exact. If instead all three rows had collisions, say counters 58, 61, 55, the reported estimate would be 55: an overestimate of 5, but still closer to the truth than any single row alone, and never below the true 50.

What this means in practice

Count-min sketches back "top-K" and heavy-hitter detection at scale: finding the most-traded symbols in a stream, estimating per-IP request rates for rate limiting, or tracking approximate order-flow volume per instrument in a system where allocating a real counter per instrument would be wasteful. The error is controlled by table size — more columns $w$ shrinks the average collision damage, more rows $d$ shrinks the chance an unlucky row dominates the minimum — so accuracy is a memory dial, not a fixed property of the algorithm.