Count-Min Sketch

What does Count-Min guarantee, and why is it accurate for the head and meaningless for the tail?

A Count-Min Sketch estimates how many times each item appeared in a stream, in fixed memory.

The structure. A table of d rows and w columns of counters. Hash each item once per row (each row has its own hash function) and increment the one counter it lands on in every row. To estimate an item's count, take the minimum across its d counters. Collisions with other items can only add to a counter, so the minimum is the tightest available overestimate.

class CountMin:
    def __init__(self, w, d):
        self.w, self.d = w, d
        self.t = [[0] * w for _ in range(d)]
    def add(self, x, c=1):
        for r in range(self.d):
            self.t[r][hash((r, x)) % self.w] += c
    def estimate(self, x):
        return min(self.t[r][hash((r, x)) % self.w] for r in range(self.d))

The guarantee, stated precisely, because the imprecise version causes real damage. Choose w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉. Then the estimate exceeds the true count by at most ε · N with probability 1 − δ, where N is the total number of events in the stream (the L1 norm of the frequency vector), not the item's own frequency.

Count-Min is a heavy-hitter structure that happens to accept point queries. It is not a frequency oracle. Anyone using it to answer "how many times did this specific rare key appear" is reading random numbers with confidence.

Memory for this example. ε = 0.001 gives w = ⌈2.718 / 0.001⌉ = 2,719. With δ = 1% (so d = ⌈ln 100⌉ = 5) the table has 5 × 2,719 ≈ 13,600 counters, about 54 KB with 4-byte counters, whatever the stream size.

It is a linear sketch, and linearity buys mergeability. The sketch is a fixed random projection matrix applied to the frequency vector. So sketch(A) + sketch(B) = sketch(A ⊎ B) exactly: add the two tables cell by cell and you have the sketch of the combined stream. This is the general rule for the whole article and it is worth stating as a principle, which we call the Homomorphism law:

Count-Sketch, the signed variant (each item adds +1 or −1 per row, chosen by a second hash), extends this to subtraction, and therefore to deletions and to estimates of the second moment.

Count-Min is not idempotent. Duplicate delivery inflates it directly.

Count-Mean-Min deserves one line: subtract each row's expected noise (N/w) before taking the median, rather than the minimum. On skewed data this substantially reduces the bias that the minimum estimator carries.