Count-Min Sketch

Introduction

Tracking exact frequencies of elements in a high-volume data stream is expensive.
If you need to know how many times each IP address appeared in a network log, or how many times each word was queried in a search engine, maintaining a full hash map requires memory proportional to the number of distinct elements.
In distributed systems processing millions of events per second, this cost becomes prohibitive.

The Count-Min Sketch (CMS) is a probabilistic data structure that answers frequency queries using sublinear space.
It trades exact accuracy for bounded, one-sided error: it may overestimate counts but never underestimates them.
This property, combined with its simplicity and composability, has made it a foundational tool in stream processing, network monitoring, and database query optimization.

How It Works

A Count-Min Sketch consists of a two-dimensional array of counters with d rows and w columns, initialized to zero.
Each row is associated with an independent hash function that maps elements to one of the w columns.

When an element arrives, it is hashed by each of the d hash functions and the corresponding counter in each row is incremented.
To query the estimated frequency of an element, you hash it with the same d hash functions and return the minimum value across all d rows.
This is the origin of the name: Count (increment counters), Min (take the minimum on query).

Parameters and Error Bounds

The sketch is parameterized by two user-chosen values:

• ε (epsilon): controls the accuracy of the estimate. The width is set to w = ⌈e/ε⌉, where e is Euler's number (~2.718).
• δ (delta): controls the probability that the error bound is exceeded. The depth is set to d = ⌈ln(1/δ)⌉.

Given these parameters, for any element a with true frequency f(a), the estimate f̂(a) satisfies:

f(a) ≤ f̂(a) ≤ f(a) + ε·N

with probability at least 1 - δ, where N is the total count of all elements inserted.
The overestimation comes from hash collisions: other elements that hash to the same positions inflate the counters.
Taking the minimum across d independent hash functions reduces the chance that all rows suffer from heavy collisions simultaneously.

Space Complexity

The total space is O(w × d) = O((1/ε) × ln(1/δ)).
This is independent of the number of distinct elements, which is what makes it practical for high-cardinality streams.
For example, with ε = 0.001 and δ = 0.01, the sketch requires ⌈e/0.001⌉ = ⌈2718.28⌉ = 2719 columns and ⌈ln(100)⌉ = ⌈4.605⌉ = 5 rows, giving 2,719 × 5 = 13,595 counters.
Even with 4-byte counters, that is about 53 KB, regardless of whether the stream contains thousands or billions of distinct elements.

Algorithm

Update (Increment)

function UPDATE(sketch, element, count=1):
    for i in 0 to d-1:
        j = hash_i(element) mod w
        sketch[i][j] += count

Query (Estimate Frequency)

function QUERY(sketch, element):
    min_val = +∞
    for i in 0 to d-1:
        j = hash_i(element) mod w
        min_val = min(min_val, sketch[i][j])
    return min_val

Merge (for distributed aggregation)

function MERGE(sketch_A, sketch_B):
    // Both sketches must have the same dimensions and hash functions
    for i in 0 to d-1:
        for j in 0 to w-1:
            result[i][j] = sketch_A[i][j] + sketch_B[i][j]
    return result

Both UPDATE and QUERY run in O(d) time, which is O(ln(1/δ)).
With typical values of δ, this means 5-10 hash computations per operation.
The MERGE operation is O(d × w) and produces a sketch that is mathematically equivalent to one that had observed the union of both input streams.

Practical Considerations

Hash Function Selection

The original analysis by Cormode and Muthukrishnan requires pairwise independent hash functions.
In practice, fast hash families like MurmurHash3 or xxHash with different seeds per row work well.
Using a single hash with row-specific bit partitioning is another common technique that reduces computation time.

One-Sided Error and Its Implications

The guarantee that estimates never undercount is crucial for certain applications.
If you use a CMS to detect heavy hitters (elements exceeding a frequency threshold), false positives are possible — an element below the threshold may be incorrectly flagged — but false negatives are not: every element whose true frequency exceeds the threshold will be identified.
This makes CMS suitable for conservative filtering: flag candidates with the sketch, then verify them with exact counts if needed.

Conservative Update

A widely used optimization called conservative update reduces overestimation in practice.
Instead of unconditionally incrementing all d counters, you first query the current minimum estimate, then only update counters that are at or below that minimum (raising them to min_val + count).
This ensures counters that are already inflated above the new minimum are not inflated further.
Note that the minimum is computed once before any updates, so all rows use the same pre-update baseline.
Conservative update does not change the worst-case bounds but significantly reduces average error.

function CONSERVATIVE_UPDATE(sketch, element, count=1):
    // Query the current minimum BEFORE making any updates
    min_val = QUERY(sketch, element)
    for i in 0 to d-1:
        j = hash_i(element) mod w
        // Only raise counters that are at or below the current minimum estimate
        sketch[i][j] = max(sketch[i][j], min_val + count)

Comparison with Other Sketches

The Count-Min Sketch is often compared to the Count Sketch (Charikar et al., 2002), which uses an additional random sign (+1 or -1) per hash function and accumulates signed counts.
Count Sketch provides unbiased estimates (errors can be positive or negative), while CMS provides biased but one-sided estimates.
Count Sketch can be more accurate for point queries on elements with moderate frequency, but CMS is generally preferred when the one-sided error property is useful and when simplicity of implementation matters.

Bloom filters answer membership queries ("has this element been seen?"), while CMS answers frequency queries ("how many times has this element been seen?").
Although both use multiple hash functions to index into an array-like structure, their designs differ substantially: a Bloom filter sets bits at each hashed position within a single shared bit array, while CMS maintains independent counter arrays per hash function and takes the minimum on query.

Applications in Distributed Systems

Network Traffic Monitoring

CMS is a natural fit for identifying heavy hitter flows in network monitoring.
Each router or switch maintains a local sketch, and sketches are periodically merged at a central aggregator.
The mergeability property means no coordination is needed during the measurement interval.

Database Query Optimization

Several database engines use CMS to maintain approximate frequency histograms over columns.
Apache Spark uses CMS for frequency estimation in query planning (distinct value counts use HyperLogLog).
PostgreSQL's statistics system could conceptually be augmented with CMS for multi-column frequency estimation.

Stream Processing Pipelines

In systems like Apache Flink and Apache Kafka Streams, CMS enables approximate aggregations over unbounded streams without growing state proportional to the key space.
Time-windowed CMS instances can be used to track frequency changes over sliding or tumbling windows.

Rate Limiting and Anomaly Detection

Distributed rate limiters can use per-node CMS instances to estimate request rates by client or API key.
Because the sketch never undercounts, a rate limiter using CMS will sometimes throttle a client before it reaches the true rate threshold (due to overestimation) but will never allow a client to exceed the threshold undetected.

Content Delivery and Caching

CMS can identify "trending" or "hot" objects in a CDN by tracking access frequencies with minimal memory.
Objects whose estimated count exceeds a threshold are promoted to higher tiers of cache.
TinyLFU, used in Caffeine (a popular Java caching library), employs a Count-Min Sketch as its frequency estimator to make admission decisions.

Limitations

The primary limitation is that error scales with N, the total stream size.
For long-running streams, ε·N can become large even with a small ε.
Mitigation strategies include periodic decay (multiplying all counters by a factor less than 1) or maintaining separate sketches per time window.

CMS does not support deletion natively.
Decrementing counters risks underestimation, which violates the core one-sided guarantee.
The Count Sketch supports signed updates (incrementing with +1 or -1), which allows a form of deletion, though this comes at the cost of the one-sided error property.
Count-Min-Log variants offer additional options for certain workloads.

The sketch also cannot enumerate its contents.
You can query a specific element's frequency, but you cannot iterate over all elements that were inserted.
Finding heavy hitters requires maintaining a separate candidate set alongside the sketch.

Key Points

• Count-Min Sketch estimates element frequencies in sublinear space using d independent hash functions over w columns, returning the minimum counter value across all rows for any query.
• The error is one-sided: estimates are always greater than or equal to true frequencies, with overestimation bounded by ε·N with probability at least 1 - δ.
• Space usage is O((1/ε) × ln(1/δ)), independent of the number of distinct elements, making it suitable for high-cardinality streams.
• Sketches are mergeable by elementwise addition, enabling natural parallel and distributed aggregation without coordination.
• Conservative update is a practical optimization that reduces average overestimation without affecting worst-case guarantees.
• CMS does not natively support deletions; decrementing counters violates the one-sided error guarantee. Count Sketch supports signed updates, enabling deletion, but sacrifices the one-sided property. Count Sketch supports signed updates enabling deletion, but sacrifices the one-sided property.
• Common applications include network heavy hitter detection, database frequency estimation, distributed rate limiting, and cache admission policies.

References

Cormode, G. and Muthukrishnan, S. "An Improved Data Stream Summary: The Count-Min Sketch and its Applications." Journal of Algorithms, 55(1):58-75, 2005.

Charikar, M., Chen, K., and Farach-Colton, M. "Finding Frequent Items in Data Streams" [Count Sketch]. Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP), 2002.

Einziger, G., Friedman, R., and Manes, B. "TinyLFU: A Highly Efficient Cache Admission Policy." ACM Transactions on Storage, 13(4):1-31, 2017.

Cormode, G. and Hadjieleftheriou, M. "Finding Frequent Items in Data Streams." Proceedings of the VLDB Endowment, 1(2):1530-1541, 2008.