Count-Min Sketch counted streams by accepting one-sided error

Data streams made exact counting impractical: keeping a counter for every possible item could cost more memory than the stream processor had. Older summaries improved space, but many bounds were still too expensive.

Count-Min Sketch used a small matrix of counters and several hash functions. Updates were constant-time increments; point, range and inner-product queries were approximate, but fast and sublinear in memory.

Cormode and Muthukrishnan's publication page summarizes the improvement: for several stream problems, the space or time bound typically improved from a factor of 1/epsilon squared to 1/epsilon.

Make every error point upward

Hash collisions are tolerated instead of prevented, which makes memory fixed and predictable.

Taking the minimum across rows turns many noisy counters into a bounded overestimate.

The structure supports several stream queries, not just a single heavy-hitter report.

Its small, mergeable shape made it practical for telemetry, ads, networking and databases.

Approximation is easier to operate when its errors have a direction; one-sided error lets downstream systems treat the result as a safe upper estimate.

Count-Min Sketch became one of the standard sketches for frequency estimation in streaming systems. The clever move was not pretending collisions vanish; it arranged collisions so their damage was measurable and one-sided.