Data structures · 11 min

Count-Min Sketch

Count 500 million hashtags a day in about half a megabyte. It may overcount a little, but it never undercounts.

Here is a puzzle. Your app gets 500 million posts a day, each with a hashtag, and about 50 million different hashtags turn up. You need to know how often each one was used, so you can show what is trending.

The catch: the counting box has under 1 MB of memory. The answers may be a little off, but any count you report must be within 50,000 of the truth, at least 99 times in 100. Is that possible?

Why the obvious answer is out

The obvious way is a map from hashtag to count: see #sakura, add 1 to map["#sakura"]. It is exact and easy.

It is also huge. 50 million keys at about 16 bytes of text plus an 8-byte count is 1.2 GB, before the map’s own overhead. Worse, it grows with every new hashtag, and most hashtags are used once or twice and never matter.

So the map is ruled out. Whatever we build has to stay the same size no matter how many different hashtags show up. That means it cannot even remember the hashtags themselves.

The clue: you are allowed to be a little wrong

Look at the rule again: within 50,000. A trending hashtag is used millions of times a day, so being off by 50,000 doesn’t change what trends. A hashtag used 3 times is never going to trend, so you don’t care how wrong its count is.

That freedom is what makes the puzzle solvable.

Attempt one: let hashtags share counters

Take a row of 16 counters, numbered #0 to #15. To count a post tagged #sakura, hash “#sakura”, divide the big number by 16 and keep the remainder. That gives a number from 0 to 15. Add 1 to that counter.

To ask “how many #sakura?”, do the same hash and read the same counter. The row never grows: 16 numbers, whatever tags arrive.

But 50 million hashtags (or even 40) can’t each get their own counter out of 16. Two different tags will often land on the same one. That is called a collision, and it means the counter holds both tags’ posts added together.

Attempt two: several rows, believe the smallest

The fix is to keep a few rows instead of one, say 4 rows of 16 counters. Each row mixes its own row number into the text before hashing, so #sakura lands on a different counter in each row, and so does every other tag. Its neighbours in row 1 are strangers in row 2.

To add a post, bump one counter in every row. To read a count, look at the same 4 counters and take the smallest. That is the whole structure, and where the name comes from: count in every row, report the minimum.

Why does the smallest work? Every counter is at least the real count, because collisions only add. So the smallest is the closest. To be badly wrong, #sakura would need to share with a busy tag in every row at once, and each extra row makes that much less likely.

How wrong can it be? Two knobs

The demo just showed the pattern. The overcount on a counter is whatever other tags dumped there, so it depends on how busy the whole stream is, not on the tag you asked about.

Width (counters per row) sets how big the error can get. A good hash spreads posts evenly, so a counter holds about total ÷ width posts on average. In the demo, 1,000 posts over 16 counters is about 62 per counter.

How often is a row badly off? Pick a line at 2.72 times the average: 2.72 × 62 ≈ 170. The 16 counters hold 1,000 posts between them, so at most 5 can hold more than 170 (6 × 170 is already 1,020). Your tag lands on a random counter, so the chance that it gets more than 170 extra is at most 5 in 16.

The general rule: in any one row, the chance of more than 2.72 × total ÷ width extra is at most 1 in 2.72, which is 0.368, about 37%. (Here it came out a little lower, 5 in 16, because you can’t have a fraction of a counter. Any multiple above 1 would work; 2.72, a constant mathematicians call e, happens to need the fewest counters in total.)

Rows set how often you get unlucky. Each row mixes in its own number, so being unlucky in row 1 says nothing about row 2: they behave like separate coin flips. The estimate is only that wrong if every row is unlucky, so with 4 rows the chance is at most 0.368 × 0.368 × 0.368 × 0.368 ≈ 0.018, under 2%.

The demo’s “Worst error, usually” box shows exactly this: 2.72 × 1,000 ÷ 16 ≈ 170, and 98.2% of the time. It is a limit, not a typical result: 98.2% of the time the error stays under 170. The errors you actually saw were much smaller, because the smallest of 4 counters is usually one of the lucky ones.

Solving the puzzle

Now size it. We want the error under 50,000, which is 1 in 10,000 of our 500 million posts, and we want to be at least 99% sure.

1. Width: 2.72 × 500,000,000 ÷ 50,000 ≈ 27,200 counters per row. (Libraries use the exact e, 2.71828…, which gives 27,183.)
2. Rows: 4 rows give 98.2%, just short. With 5 the chance of a bigger error is 0.368⁵ ≈ 0.007, so 99.3% of counts are within 50,000.
3. Memory: 27,183 × 5 = 135,915 counters. A 4-byte counter holds up to about 4.3 billion, plenty for 500 million posts. That is 543,660 bytes, about 544 KB.

One gap remains. The sketch can answer “how many #sakura?” but it can’t list hashtags, because it never stored their names. So next to it keep a small list of the current top 10, with names. For each post, add it to the sketch and read its estimate. If the tag is already on the list, update its number; if not, and it beats the smallest number on the list, it replaces that one.

That is the full answer: about 544 KB of counters plus a list of 10 names, instead of 1.2 GB.

It also spreads across servers. If every server uses the same width, rows and hashes, #sakura lands on the same counters everywhere. So adding two grids counter by counter gives exactly the grid one server would have built from both streams. Each server counts its own posts, and a central job adds the grids up.

The code

Notice that add and estimate pick the same counters; one bumps them, the other takes the smallest.

width = 27183
rows = 5
grid = [[0] * width for each row]

counter(row, tag):
    return hash(row + ":" + tag) % width

add(tag):
    for row in 0 .. rows-1:
        grid[row][counter(row, tag)] += 1

estimate(tag):
    return min(grid[row][counter(row, tag)] for row in 0 .. rows-1)

Where you will meet it

• Redis has it built in: CMS.INCRBY adds, CMS.QUERY reads, CMS.MERGE combines sketches, and CMS.INITBYPROB sizes one from the error and certainty you want.
• Apache Spark builds one over a DataFrame column with df.stat.countMinSketch, to find frequent values without a full group-by.
• “Top K videos” and “trending now” designs use the sketch-plus-top-list pattern above.
• Abuse detection: count requests per IP address or API key to spot the few sending far more than everyone else.