Count-Min, and Why Sketches Compose

The third question is how many times a particular item occurred. Exactly answered by a counter per distinct item, which costs space proportional to the number of distinct items and therefore fails for the same reason as before.

The fix follows the Bloom filter's shape. Keep a fixed grid of counters, hash each item to positions, and accept that unrelated items will share counters.

Graham Cormode and S. Muthukrishnan set out the structure and its analysis in "An improved data stream summary: the count-min sketch and its applications", Journal of Algorithms, volume 55, issue 1, 2005, pages 58 to 75.

The layout is a grid: d rows and w columns, one hash function per row. To record an occurrence, hash the item once per row and increment the counter at that row's column. Every item touches exactly d counters, one in each row.

Each row alone is a hash table with collisions and no resolution, so each row's counter is the true count plus the counts of everything else that landed there. The design is entirely about combining the rows to remove that contamination.

The name states the algorithm. Increment on write, take the minimum on read.

The reasoning is short and it is the whole insight. Every counter an item touches contains that item's true count plus whatever collided there. Collisions only ever add, since counts are non-negative, so every one of the d counters is greater than or equal to the truth.

That gives the one-sided guarantee immediately: the sketch never underestimates. Taking the minimum picks the least contaminated of the d readings, which is the best available upper bound.

It also explains why adding rows helps. Each row is an independent chance for the item to land somewhere uncrowded, and only one of the d needs to be clean for the answer to be nearly exact. The probability that all d rows are badly contaminated falls exponentially in d.

So the two dimensions of the grid do different jobs. Width w controls how much contamination a typical collision contributes. Depth d controls the probability that every row is unlucky at once.

The implementation is a two-dimensional array and two loops.

import hashlib, math

class CountMin:
    def __init__(self, epsilon=0.001, delta=0.001):
        self.w = math.ceil(math.e / epsilon)      # columns: error scale
        self.d = math.ceil(math.log(1 / delta))   # rows: confidence
        self.grid = [[0] * self.w for _ in range(self.d)]
        self.total = 0

    def _cols(self, item):
        for r in range(self.d):
            h = hashlib.blake2b(item, salt=str(r).encode()[:16]).digest()
            yield r, int.from_bytes(h[:8], "big") % self.w

    def add(self, item, count=1):
        self.total += count
        for r, c in self._cols(item):
            self.grid[r][c] += count

    def estimate(self, item):
        return min(self.grid[r][c] for r, c in self._cols(item))

cm = CountMin(epsilon=0.001, delta=0.001)
cm.w, cm.d          # 2719 columns, 7 rows -> 19,033 counters, about 74 KB

At four bytes per counter that is roughly 74 kilobytes, fixed, regardless of whether the stream contains a thousand distinct items or a billion.

The two parameters are chosen from the guarantee rather than by feel, which is the subject of the next step.

The bound is what separates this from a hash table that happens to lose data, and it is worth reading carefully because it contains a trap.

With w = e/epsilon columns and d = ln(1/delta) rows, for any item, with probability at least 1 - delta:

true count  <=  estimate  <=  true count + epsilon * N

where N is the total of all counts in the stream, not the count of the item being queried.

That last clause is the trap. The error is proportional to the size of the entire stream, so it is an absolute quantity, identical for every item.

Work through what that means. In a stream totalling one billion, with epsilon at one thousandth, the error term is up to one million. For an item that genuinely occurred fifty million times, an error of a million is 2% and the answer is useful. For an item that occurred forty times, the estimate could be over a million, and the answer is worthless.

So the sketch is accurate for frequent items and meaningless for rare ones, and the boundary is set by the stream total rather than by anything about the item.

The structure is not a general frequency table with some noise. It is a heavy hitter detector, and reading it as anything else produces confident nonsense.

The canonical use follows directly. To find every item occurring more than some threshold of the stream, query candidates and keep those whose estimate exceeds it. Because the sketch never underestimates, no genuine heavy hitter is ever missed. Some light items may be wrongly included, and those are cheaply filtered by a second pass or an exact counter for the shortlist.

That is the same filter pattern from the first lesson, applied to frequency instead of membership: a one-sided error means the cheap structure can be trusted to narrow the field, and something exact resolves the remainder.

Read the right-hand branch as a hard constraint rather than a caveat. Using a count-min sketch to report the frequency of an arbitrary item, without knowing whether it is heavy, is a misuse that the structure will not signal.

Two adjustments are standard and both are worth knowing.

Conservative update. On increment, rather than adding to all d counters, first compute the current estimate, then raise each counter only to the level the new estimate requires. Counters that are already higher, because of contamination, are left alone. This adds no error, since the sketch still never underestimates, and it measurably reduces overestimation. The cost is that increments now require a read, and deletion becomes impossible.

Pairing with a heap. The sketch answers frequency for a queried item but cannot enumerate the top items, since it stores no keys. The standard construction keeps a small heap of the top k candidates alongside: after each update, if the item's estimate exceeds the heap's minimum, insert it. The sketch supplies the counts and the heap supplies the identities.

That pairing is the usual shape of a production heavy-hitters service, and it illustrates a general point about these structures. They answer one narrow question extremely cheaply, and are almost always deployed next to something small and exact that covers what they cannot do.

Now the idea that ties the cursus together, and it is the reason these structures dominate large-scale systems rather than merely appearing in them.

All three are mergeable. Two sketches built independently over two halves of the data can be combined into the sketch of the whole, by an element-wise operation, with no loss.

The third column is the remarkable part. Merging introduces no additional error. The merged sketch is bit-for-bit what you would have built by processing everything in one pass.

What that buys is the removal of coordination. A thousand machines can each sketch their own shard with no communication, and the results combine at the end. Sketches can be stored per hour and merged into any longer period on demand. A streaming job can checkpoint a sketch and resume.

That is the actual reason for their ubiquity. The space saving is what gets described; the ability to compute in parallel with zero coordination and zero loss is what makes them structural.

Four lessons, one bargain, examined three ways.

Exact answers to set questions cost memory proportional to the data, and that is a lower bound rather than an inefficiency. Giving up exactness buys constant memory, and the useful structures give it up in a specific direction: a Bloom filter only ever says yes wrongly, a count-min sketch only ever counts too high, and HyperLogLog is wrong by a bounded proportion.

Directional error is what makes them safe to build on. A one-sided answer can be resolved by something exact behind it, so the system as a whole stays correct while the expensive path is taken only when necessary.

And mergeability is what makes them scale. Element-wise combination with no loss means the computation distributes without coordination, which is a stronger property than the space saving and less often mentioned.

The transferable question, when you next meet a resource limit: rather than asking how to store this more compactly, ask what you actually need to answer, and which direction you can afford to be wrong in. That reframing is what produced all three of these, and it produces others.