Count-Min Sketch Visualization | Hash Rows, Counters, Overestimates

The idea: a table of counters that never under-counts

A count-min sketch answers "how many times have I seen this item?" for a stream far too big to count exactly. It stores no items, only a table of d rows × w counters, and gives each row its own hash function. The answer can be too big, never too small.

estimate of cat goes through three hash functions giving columns 0, 6 and 3 of a 3 by 8 table of counters. The counters read 2, 3 and 2. The 3 is red because dog shares that counter. The min box says min(2, 3, 2) = 2, and the true count is 2 — After cat, cat, dog: row 2 says 3 because dog shares the counter, but the min of the three rows is the true count, 2.

The page has one sketch of d = 3 rows and w = 8 counters. Pick a word and press Add or Query. Under each counter are the words that hash to it. The true counts below the sketch are kept only to check every estimate; a chip turns red when the sketch over-counts that word.

increment and estimate

increment(x, c): for each row r, compute h_r(x) and add c to that counter. One counter per row changes (Redis: CMS.INCRBY key x c).
estimate(x): read the same d counters and return the smallest (Redis: CMS.QUERY key x).

Adding cat twice puts 2 in one counter of each row, and the query reads min(2, 2, 2) = 2 (Demo 1). Each row uses a hash from a pairwise-independent family: v = FNV-1a(x) mod 65521 and h_r = ((a_r·v + b_r) mod 65521) mod 8, with different a_r, b_r per row. Different rows send two words to the same counter only by chance, and rarely in every row.

Why the min, and why it over-counts

A counter holds the sum of every word that hashes to it. Other words can only add, so every counter is ≥ the true count, and so is their min. The min is the row with the fewest collisions. After cat, cat, dog, row 2 says 3 because dog lands on cat's counter, but rows 1 and 3 say 2, so the answer is exact (Demo 2).

When an item collides in every row, the min is too big. koi was never added, but bee, fox and owl each hit one of koi's counters, so estimate("koi") = 1 (Demo 3). This is the count-min version of a Bloom filter's false positive.

After bee, fox and owl are added, koi's three counters are row 1 column 3 holding bee, row 2 column 5 holding fox and row 3 column 0 holding owl. All three read 1, so min(1, 1, 1) = 1 although koi's true count is 0 — A word that was never added reads 1: each of its three counters was hit by a different word.

Choosing w and d

Cormode and Muthukrishnan show that with w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, each estimate is at most true + εN with probability at least 1 − δ, where N is the total of all increments. Width controls how big the error can be; depth controls how often it is that bad. The memory is w·d counters, whatever the number of distinct items.

w × d	ε = e/w	δ = e^−d	error bound for N = 1,000,000
8 × 3 (this page)	0.34	5.0%	340,000
2,000 × 5	0.0014	0.67%	1,359
20,000 × 7	0.00014	0.09%	136

In Demo 4 a stream of N = 10 items (cat ×3, owl ×2, ant, elk, emu, gnu, dog) gives a bound of εN = 3.4. dog reads 3 instead of 1 and ant 2 instead of 1; every other word is exact. The error is relative to N, so the sketch is good for frequent items and poor for rare ones.

Conservative update

A standard increment adds c to all d counters, even those already too big. Conservative update first reads the estimate m, then raises each counter only to max(counter, m + c). Counters that are already high are left alone (grey on the canvas). The estimate stays an upper bound, and the errors get smaller. On the same stream, dog reads 2 instead of 3 and ant is exact (Demo 5). The price: an increment needs a read first, and negative updates (decrements) are no longer allowed.

Count-min, Bloom filter and HyperLogLog

Sketch	Question	Cells	Error
Bloom filter	Have I seen x?	m bits, k hashes	false "yes"
Count-min sketch	How often did I see x?	d × w counters, one hash per row	count too big
HyperLogLog	How many distinct items?	m small registers	about 1.04/√m either way

A count-min sketch with d = 1 is a counting Bloom filter with one hash; a Bloom filter is what you get if each counter is cut to one bit. See Bloom Filter for set membership, HyperLogLog for counting distinct items, and Open Hash Tables for exact counts that cost memory per item.

Real uses

Heavy hitters and top-k: keep a small heap of the items with the highest estimates (Redis TOPK).
Network monitoring: bytes per source IP in a router, to spot a flood without a table per flow.
Databases and caches: frequency estimates for query planning, and the admission filter of the TinyLFU cache policy (Caffeine).
Redis Stack: CMS.INITBYDIM key width depth, CMS.INCRBY, CMS.QUERY, and CMS.MERGE, which adds two sketches cell by cell.

What the page leaves out

Real sizes (thousands of counters per row) and fast hashes such as MurmurHash; count-mean-min and other ways to subtract the expected noise; decrements and the count-min's use for inner products and range queries; counter overflow and the 4-bit counters of TinyLFU with periodic halving; and the Count sketch, which can err in both directions but is unbiased.