Count-Min Sketch: Estimating Frequencies Without Storing Everything

Why Exact Counting Falls Apart at Scale

Counting exactly how many times each item appears in a stream sounds simple: keep a hash map from item to count, and increment the corresponding entry on every occurrence. The problem is memory. If a stream contains hundreds of millions of distinct items, such as unique IP addresses hitting a server, unique search queries, or unique product IDs in a retail feed, the hash map itself grows to hold every single key, plus overhead for pointers, buckets, and collision chains. In many real systems the number of distinct items is unbounded or unknown in advance, and the stream never stops, so there is no point at which you could simply stop growing the map. Worse, many applications only care about approximate answers: is this IP address a heavy hitter, is this query unusually popular, is this product trending. For these questions, spending gigabytes of RAM to get a perfectly exact count is wasteful when a slightly fuzzy answer computed with a few kilobytes would do just as well. This is the gap the Count-Min Sketch fills. It gives up exactness in exchange for a fixed, tunable memory budget that does not grow with the number of distinct items, only with the desired accuracy and confidence level, making it practical for streams of effectively unlimited size and cardinality.

The Structure: A Grid of Counters and Several Hash Functions

A Count-Min Sketch is, at its core, a two-dimensional array of counters with d rows and w columns, all initialized to zero. Each row has its own independent hash function that maps any incoming item to one of the w columns in that row. Crucially, the rows do not represent different items or different time periods; they are parallel, independent views of the same stream, each using a different hash function to scatter items across its columns. Because the hash functions are independent, an item that happens to collide with another item in one row's hash function will very likely not collide with that same item in a different row's hash function. This redundancy is the entire trick behind the structure: no single row can be trusted on its own because collisions inflate its counters, but combining information across all d rows lets the sketch cancel out most of that noise. The size of the grid, meaning the number of rows and columns, is chosen ahead of time based on how much error is tolerable and how confident you need to be that the error stays within that bound, and that size stays fixed no matter how many distinct items eventually pass through the stream.

Updating the Sketch: Hash, Then Increment

Processing a new occurrence of an item is extremely cheap. For each of the d rows, the item is passed through that row's hash function to compute a column index, and the counter sitting at that row and column position is incremented by one. This happens once per row, so a single update touches exactly d counters total, regardless of how many distinct items exist in the stream or how large the grid is. There is no lookup of an existing entry, no resizing, no chaining, and no need to even know whether the item has been seen before. Two entirely different items can, and often will, land in the same column in a given row purely by hash coincidence, and when that happens their counts get mixed together in that cell. This is expected and tolerated, because the sketch is designed so that even though individual cells may be contaminated by collisions from other items, the combination of all rows during a query can still recover a tight and reliable estimate. The update operation's cost stays constant over the life of the stream, which is exactly what makes the structure suitable for high-throughput, real-time environments where every event must be processed in a fixed, small amount of time.

Querying the Sketch: Why the Minimum Is the Right Answer

To estimate how many times an item has appeared, the sketch hashes that item using each row's hash function exactly as it did during updates, looks up the counter value at each resulting position, and then reports the minimum of those d values as the frequency estimate. The reasoning behind choosing the minimum, rather than the average or the maximum, comes down to the one-directional nature of the error involved. Every counter in the grid can only be inflated by collisions with other items sharing that same cell; a collision can never cause a counter to undercount, since counters only ever get incremented, never decremented. This means that in every single row, the counter value at an item's hashed position is guaranteed to be greater than or equal to the item's true count, because it equals the true count plus whatever extra increments came from colliding items. Since the true count is a lower bound in every row, and different rows tend to suffer from different, largely independent collisions, the row with the least contamination will produce the value closest to the truth. Taking the minimum across all rows therefore selects the tightest, least-inflated estimate available, and it is mathematically guaranteed that the true count is always less than or equal to this minimum, so the estimate never falls below reality, it can only ever be equal to or slightly above it.

Trading Memory for Accuracy, and Where It's Used

The accuracy of a Count-Min Sketch is governed directly by its dimensions. Increasing the number of columns, w, spreads items more thinly across each row, reducing the chance that any two items collide and thereby shrinking the typical amount of over-counting. Increasing the number of rows, d, adds more independent chances to find a row where a given item escaped serious collision, which boosts the confidence that the minimum returned is close to the true value. Doubling either dimension roughly doubles memory use but yields a corresponding improvement in either the error bound or the confidence level, giving engineers a simple dial to trade memory for precision based on what their application can tolerate. In practice, this structure shows up constantly in systems that must summarize enormous streams cheaply. Network operators use it to monitor traffic and flag heavy hitters, meaning IP addresses or connections consuming disproportionate bandwidth, without keeping per-flow state for every possible address. Database query optimizers use sketches built over table columns to estimate how many rows a filter or join will match, which guides the choice of execution plan without scanning the full table. Streaming analytics platforms use it to answer questions like which events, users, or hashtags are trending in real time, processing millions of events per second while keeping memory usage flat and predictable.

Frequently asked questions

Try it live

Everything above runs in your browser — open Count-Min Sketch: Estimating Frequencies Without Storing Everything and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.