Skip to main content
Be Bitwise

Count-Min Sketch

Bloom Filters & Probabilistic Data Structures · Data & Hashing track

5 min read

In this module

Counting in a Firehose

Picture yourself watching a backbone router. Millions of packets a second blow past, and you'd quite like to know which IP addresses are responsible for the most. Storing a counter per source address won't fly — that's 4 billion buckets just for IPv4, never mind IPv6. So you need a frequency estimator that runs in bounded memory.

A count-min sketch is exactly that: a probabilistic structure for estimating how often each element appears in a stream. It uses multiple hash functions, like a bloom filter, except the cells store counters rather than single bits.

Structure

The sketch is a 2D array of counters: d rows by w columns. Every row gets its own independent hash function.

text
col 0 col 1 col 2 col 3 col 4 col 5 col 6 col 7
row 0: [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]
row 1: [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]
row 2: [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]

Insertion

To log an occurrence, run the element through each row's hash and bump the counter you land on in that row.

text
record("192.168.1.1"):
hash0("192.168.1.1") % w = 3 --> increment row 0, col 3
hash1("192.168.1.1") % w = 7 --> increment row 1, col 7
hash2("192.168.1.1") % w = 1 --> increment row 2, col 1

After seeing "192.168.1.1" five times:

text
col 0 col 1 col 2 col 3 col 4 col 5 col 6 col 7
row 0: [ 0 ] [ 0 ] [ 0 ] [ 5 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]
row 1: [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 5 ]
row 2: [ 0 ] [ 5 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ]

Query

To estimate how often an element has been seen, hash it through each function, read the counter in each row, and return the minimum.

text
query("192.168.1.1"):
row 0, col 3 = 5
row 1, col 7 = 7 (inflated by collisions from other elements!)
row 2, col 1 = 5
estimate = min(5, 7, 5) = 5 --> correct!
Key Concept

A count-min sketch returns the minimum counter across all rows as its frequency estimate. Counters only ever drift upwards from collisions, never downwards, so the smallest value sits closest to the truth. The sketch never undercounts. It can overcount, but the error is bounded and tunable.

Why the Minimum Works

Collisions push counters up. As long as you only ever add to the counts, they can't push them below the true count. So picking the smallest of d counters is picking the one that suffered the fewest collisions. Columns and rows do different jobs, though: more columns shrink the error, while more rows only make a bad estimate less likely.

Error Bounds

The standard result (Cormode and Muthukrishnan, 2005) is stated in terms of an error factor epsilon and a failure probability delta. Pick w = ⌈e / epsilon⌉ columns and d = ⌈ln(1 / delta)⌉ rows, and for any element with true count c, out of a stream of N events in total:

text
estimate >= c (never undercounts)
estimate <= c + epsilon * N (with probability at least 1 - delta)

More columns (w) shrink the magnitude of any individual error. More rows (d) raise your confidence that the answer landed close to the truth. For epsilon = 0.01 and delta = 0.01 that's w = 272 and d = 5.

The program below builds exactly that sketch and feeds it 200,000 events: two heavy hitters and a long tail of rare keys. Before running it, predict which keys will show the worst overcount relative to their true count.

Try itCompare true counts with estimates, then shrink W or D and see which one hurts more.
C (GCC 9.2.0)

Every key picks up a few hundred phantom counts, well inside the epsilon · N bound. For the heavy hitters that's under 2%; for a key seen eight times it's an estimate dozens of times too big. A count-min sketch is good at "who are the big talkers?" and poor at "how rare is this one?"

Practical Uses

Network monitoring. Find the top talkers — the addresses pumping the most traffic — without budgeting RAM for a per-IP counter.

Natural language processing. Word-frequency counts on corpora that wouldn't fit in any hash table on Earth.

Database query optimisation. A planner that knows which values dominate a column writes better plans for the queries that touch it.

Anomaly detection. Need to spot when something's frequency spikes? A count-min sketch keeps a running estimate cheaply enough to do it on every event.

Space Comparison

For counting 1 million distinct elements:

  • Exact hash table: ~40 MB (keys + counts + overhead)
  • Count-min sketch (epsilon=0.01, delta=0.01): 272 × 5 = 1,360 counters, about 5 KB with 32-bit counters

The sketch's size depends only on epsilon and delta, not on how many distinct elements turn up. The price is that its error grows with the total stream length, so for a fixed absolute error you need more columns as the stream grows. Even so, thousands of times less memory is typical. On a streaming pipeline pushing billions of events, that ratio is often the difference between "ships next quarter" and "doesn't ship".

When to Reach for a Count-Min Sketch

Count-min sketches shine on high-volume streams where exact counts would dwarf the memory budget. They're especially good in pairs. Drop one alongside a heap, let the sketch track frequencies and the heap track the top-k entries, and out falls a respectable approximate "heavy hitters" algorithm.

The honest question to ask yourself first: can your application live with overcounts? Financial transactions and vote counts cannot. A telemetry dashboard that's off by half a percent at a million events per second absolutely can.