Count-min sketch and top-k heavy hitters: an interactive simulator

A count-min sketch estimates how many times each item appears in a stream, such as mentions of each hashtag or clicks on each ad, in a small fixed amount of memory. It never counts too low, only too high, and the overcount is bounded. Paired with a small heap of candidates, it finds the top k heavy hitters of a stream far too large to count exactly.

The playground counts a million mentions of 50,000 hashtags. Change the width and the number of rows, and compare the sketch’s top 10 and its estimates with the true counts.

How a count-min sketch works

1. Set up d rows of w counters, all zero, and a different hash function for each row.
2. Add an item by hashing it once per row and adding its count to that counter in every row.
3. Estimate an item’s count by taking the smallest of its d counters.

Every counter an item lands in holds its own count plus whatever else hashed there, so each is an overestimate, and the smallest is the least polluted. With width w, the overcount is at most about e/w of the whole stream; with depth d, the chance of exceeding that falls like e^−d.

Width and depth do different jobs

Width sets the size of the error: with 1,000 counters per row the bound is about 2,700 of the million mentions; with 10,000, about 270. Depth protects against bad luck: with one row, a rare hashtag that happens to share a counter with the most popular one inherits its 87,000 mentions, and the playground’s single row of 1,000 gets only 1 of the top 10 right. Four rows of 1,000, 16 KB in all, get all 10, because a rare hashtag would have to collide with a popular one in every row at once.

The error is relative to the whole stream, not to the item, so heavy hitters are counted almost exactly while rare items can be overcounted many times over: hashtags with under 90 mentions are overcounted by hundreds on average at 16 KB. That is why the sketch is good for finding the top items, not for small counts.

Finding the top k in a stream

The sketch alone cannot list items; it only answers questions about items you name. To find the heaviest, keep a min-heap of the current top k: after adding each item, look up its estimate, and if it beats the smallest in the heap, put it in. Memory stays at the sketch plus k entries. Space-Saving and Misra-Gries are alternatives that track candidates directly. Exact top k needs a count for every distinct item, which is what the sketch exists to avoid.

Merging and windows

Sketches with the same width, depth and hash functions merge by adding counters, so each server or partition can count its own share and a coordinator adds them. For “trending in the last hour”, keep one sketch per minute and add the last 60, or decay counts over time.

A count-min sketch in code

import heapq, math

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

    def _slots(self, item):
        return [hash((row, item)) % self.w for row in range(self.d)]   # one hash per row

    def add(self, item, count=1):
        for row, i in enumerate(self._slots(item)):
            self.rows[row][i] += count

    def estimate(self, item):
        return min(self.rows[row][i] for row, i in enumerate(self._slots(item)))

def top_k(stream, k=10):
    cms, heap, seen = CountMinSketch(), [], set()   # heap of (estimate, item), smallest first
    for item in stream:
        cms.add(item)
        est = cms.estimate(item)
        if item in seen:
            heap = [(est if x == item else e, x) for e, x in heap]; heapq.heapify(heap)
        elif len(heap) < k or est > heap[0][0]:
            if len(heap) == k: seen.discard(heapq.heappop(heap)[1])
            heapq.heappush(heap, (est, item)); seen.add(item)
    return sorted(heap, reverse=True)

In a system design interview

For “top 10 trending hashtags” at scale, say why not exact and what the error means: “Each stream processor keeps a count-min sketch per minute, 4 rows of 10,000 counters, 160 KB, plus a heap of its top 100 candidates. A coordinator merges the sketches and heaps for the last hour. The sketch overcounts by at most a few hundred in ten million mentions, which never changes who is in the top 10, and the exact counts shown on the page come from a batch job later.” Expect the follow-ups: sliding windows, how much error is acceptable, and spam that tries to game the counts.

Read the guide to probabilistic data structures, try HyperLogLog for counting distinct items instead, or watch a strong candidate design an ad click aggregator.

Questions people ask