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.
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.
