Count-min sketch

HyperLogLog answers "how many distinct items?" A count-min sketch answers a different question: "how often did each item appear?" It keeps a fixed-size table of counters, no matter how many distinct items pass through. Its estimates never fall below the true count. They can run high, and the amount is bounded.

The big idea

The sketch is a grid of counters with d rows and w columns. Each row has its own hash function that maps an item to one column.

• Update(item): for each row, add to the counter at that row's column for the item.
• Query(item): look up the item's counter in each row, and return the minimum.

Hash collisions can only add to a counter, never subtract. So every counter is at or above the true count, and the minimum across rows is the least-polluted one.

Walking through a small sketch

Here is a sketch with 50 columns and 4 rows. It sees 2,000 rare tags once each, and #worldcup 500 times. That is 2,500 events in total.

import hashlib, math

class CountMinSketch:
    def __init__(self, width: int, depth: int):
        self.w, self.d = width, depth
        self.table = [[0] * width for _ in range(depth)]

    def _col(self, row: int, item: str) -> int:
        digest = hashlib.blake2b(item.encode(), digest_size=8,
                                 salt=row.to_bytes(8, "big")).digest()
        return int.from_bytes(digest, "big") % self.w

    def add(self, item: str, count: int = 1):
        for row in range(self.d):
            self.table[row][self._col(row, item)] += count

    def estimate(self, item: str) -> int:
        return min(self.table[row][self._col(row, item)] for row in range(self.d))

cms = CountMinSketch(width=50, depth=4)
for i in range(2000):
    cms.add(f"tag-{i}")
cms.add("#worldcup", 500)
print("#worldcup:", cms.estimate("#worldcup"))
print("tag-7:", cms.estimate("tag-7"))
print("never-seen:", cms.estimate("never-seen"))

Output:

#worldcup: 530
tag-7: 34
never-seen: 37

The sketch overestimates every time. #worldcup is 530 against a true 500. tag-7 is 34 against a true 1, and never-seen is 37 against a true 0. The table is small, so collisions are heavy. A wider table would shrink the errors.

Sizing it from an error bound

The guarantee is stated relative to N, the total number of events, not the count of one item:

true(x) ≤ estimate(x) ≤ true(x) + ε·N     with probability at least 1 − δ

width   w = ⌈e / ε⌉
depth   d = ⌈ln(1 / δ)⌉

Say you see 10 million hashtag events per hour, and want every count within ±1,000 (so ε = 1,000 / 10,000,000 = 0.0001) with 99% confidence (δ = 0.01).

w = ⌈2.718 / 0.0001⌉ = 27,183 columns
d = ⌈ln(100)⌉        = ⌈4.6⌉ = 5 rows
counters = 27,183 × 5 = 135,915
memory   ≈ 135,915 × 4 bytes ≈ 544 KB

That is 544 KB, however many distinct hashtags appear.

Where it is accurate, and where it is not

The error is relative to the total N, not to each item's count. So the sketch is accurate for frequent items and useless for rare ones. An item seen 50 times can be reported as 900 when N is large.

That makes it a good fit for heavy hitters: the most frequent items. Pair it with a small min-heap of size k. For each event, update the sketch and query the item's estimate. If the estimate beats the smallest count in the heap, put the item in the heap. This finds trending topics, the top senders in network monitoring, and hot keys in a cache.

A common improvement is conservative update. It increments only the counters that equal the current minimum. That reduces overcounting without changing the guarantee.

Common mistakes

• Expecting exact counts for rare items. Errors scale with N, so rare items are noisy.
• Using it for billing. Overcounting is possible, and billing needs exact counts.
• Sizing with a wrong ε. Compute ε as the error you accept divided by N, not as a percentage of one item.

Check yourself

1. Why can a count-min estimate never be below the true count? Collisions only add to counters. Taking the minimum across rows removes the most-polluted values but never subtracts.
2. With N = 10 million and ε = 0.0001, what is the largest error you can expect? About 1,000 (ε × N), with probability at least 99% when the depth is 5.

Key takeaways

• A count-min sketch estimates item frequencies in fixed memory. It never underestimates.
• Each row is a hash-indexed counter. The answer is the minimum across rows.
• The error bound is ε × N, so the sketch works best for frequent items.
• Pair it with a min-heap to find the top items in a stream.

Further learning

Next, read reservoir sampling to keep a fair random sample from a stream, a different tool for a different question.