Skip to content
An Improved Data Stream Summary: The Count-Min Sketch and its Applications 3 min

Graham Cormode, S. Muthukrishnan · Journal of Algorithms 2005

An Improved Data Stream Summary: The Count-Min Sketch and its Applications

A fixed size grid of counters that estimates how often any item appeared in a huge stream, never too low and rarely much too high. Feed it a stream and ask.

Read the original paper

Algorithms · Yellow Belt · Pro · 3 min read

An Improved Data Stream Summary: The Count-Min Sketch and its Applications

How do you count something a billion times a day, when you cannot afford one counter per thing? Think of the most visited web pages, the busiest IP addresses, or the hottest search terms. The number of different items is huge, and a table of exact counts would not fit in memory.

In 2005 Graham Cormode and S. Muthukrishnan introduced the Count-Min sketch, a tiny grid of numbers that answers "about how many times did this item appear?" with a guaranteed small error. It never needs to remember which items it has seen.

A Count-Min sketch is a table with a few rows of counters. Each row has its own hash function. To count an item, add one to one counter in every row. To ask for a count, read the item's counters and return the smallest. The answer is never too low, and it is too high by only a small amount, with high probability.

A grid of counters

The sketch has d rows and w columns of counters, all starting at zero. The paper picks d different hash functions, one per row, each mapping an item to a column. To record an event for an item, add one to the counter the item hashes to in each row.

The Count-Min sketch is a small grid of counters with several rows. Each row has its own hash function. An event adds one to a single counter in every row, chosen by that row's hash of the item.

Many items share each counter, because there are far more items than columns. That sharing is what keeps the table small, and it is also the only source of error.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • Counting first, then taking the minimum
  • What it is good at

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.