📊Count-Min Sketch

NEW

Also known as: CMS

A probabilistic data structure that estimates item frequencies in data streams using sublinear space with controllable overestimation error.

DESCRIPTION

Count-Min Sketch maintains a 2D array of counters indexed by multiple hash functions, incremented on each observed item. Frequency queries return the minimum across hashed counters, yielding an upper-bound estimate with tunable error and confidence. It is fast, mergeable, and supports streaming heavy-hitter detection and approximate joins. Errors are one-sided (overestimation) and depend on counter width and depth. Proper hashing and parameter selection are crucial for accuracy.

ALTERNATIVE DEFINITIONS

Wikipedia

The count–min sketch is a probabilistic sublinear-space data structure that can be used to approximately count the frequencies of events in a data stream.

Concise definition emphasizing streaming and sublinear space.

Source

Apache DataSketches

Sketches provide approximate answers for streaming analytics with known error bounds, supporting operations like frequency estimation and heavy hitters in sublinear space.

Places CMS within the broader family of streaming sketches with error guarantees.

Source

RELATED TERMS

Bloom Filter Heavy Hitters Streaming Algorithms Frequency Estimation Hash Function

COMPETING TERMS

Count Sketch Space-Saving Algorithm

KNOWLEDGE AREAS

Data Engineering Mathematics Data Science Real-time & Streaming Data

TARGET AUDIENCE

Data Engineer Data Scientist MLOps Engineer

EXTERNAL SOURCES

• Wikipedia - Count–min sketch
• Wikipedia - Overview of algorithm and properties.
• AddThis stream-lib - Developer docs and usage examples.
• DIMACS - Original Count-Min Sketch paper.

TOP QUESTIONS

What does Count-Min Sketch estimate?

It estimates item frequencies in a stream with a one-sided error that overestimates true counts, controlled by width and depth parameters.

Category: Definition

How do you tune Count-Min Sketch accuracy?

Increase width to reduce error and depth to improve confidence. Choose strong, independent hash functions to reduce collisions.

Category: Implementation

How does Count-Min Sketch compare to Count Sketch?

Count Sketch uses signed counters to yield unbiased estimates and is better for heavy hitters under certain distributions, while CMS provides upper bounds.

Category: Alternatives

Can Count-Min Sketch be merged across nodes?

Yes. Merge by element-wise addition of corresponding counters, enabling distributed analytics.

Category: Management

What are common mistakes using Count-Min Sketch?

Using too-small width causing large overestimation or poor hash functions that increase collisions. Always validate error bounds.

Category: Mistakes

When should I not use Count-Min Sketch?

Avoid when exact counts are required or memory is sufficient for precise structures; consider exact aggregations or alternative sketches.

Category: Risk

What is a typical use case for Count-Min Sketch?

Streaming frequency analysis like top URLs, query terms, or fraud signals where approximate counts suffice.

Category: Example

Is Count-Min Sketch suitable for deletions?

It can support decrements but negative counts and collision effects complicate semantics; specialized variants or Count Sketch may be preferable.

Category: Opinion

What is a hot topic around Count-Min Sketch?

Hybrid approaches combining CMS with heavy-hitter algorithms and adaptive hashing for non-stationary streams.

Category: Topic