Count-Min sketch
A Count-Min sketch is a grid of d rows by w columns of counters, with one hash function per row. Every item in a stream adds one to its own cell in every row. To estimate how often an item appeared, read its cell in each row and take the smallest of them. Because a counter can only ever have been added to, every one of those d cells is an upper bound on the item’s true count — so the minimum is too, and the estimate is never below the truth.
When it is the right choice
When a stream is too large to count exactly and the heavy items are the interesting ones: the most-requested URLs, the busiest source addresses, the most-searched terms. The sketch’s size is fixed in advance and does not grow with the stream, which is the property that makes it usable at all at that scale.
How it works
- Keep a d by w grid of counters, all zero, with one hash function per row.
- For each item in the stream, add one to the cell its row hash points at, in every row.
- To estimate an item, read its cell in each of the d rows.
- Take the smallest of those d values. That is the estimate.
Worth noticing
- The error is one-sided and it is the mirror of a Bloom filter’s: a Bloom filter never says "absent" about a member, and a sketch never says "fewer" about a count.
- A heavy item is usually exact, because the noise added to it by everything else is small next to its own count. A rare item can be wrong by a large multiple while still being wrong by a small absolute amount — which is the same error, read two ways.
- Every row holds the whole stream’s total, because each item added one to exactly one cell in every row. That is a useful thing to check a sketch against, and a useful way to see that extra rows buy confidence rather than capacity.
Cost
- Best
- O(d)
- Average
- O(d)
- Worst
- O(d)
- Space
- O(d·w)