# Count-Min Sketch with Conservative Updates: Worst-Case Analysis

arXiv: https://arxiv.org/abs/2405.12034 · HTML: https://mlsanity.com/paper/2405.12034/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2024.

## Built on by (most cited first, 1 of 1)

- [On the (Generative) Linear Sketching Problem](https://mlsanity.com/paper/2603.14474/) (2026)

## Abstract (arXiv)

Count-Min Sketch with Conservative Updates (CMS-CU) is a memory-efficient hash-based data structure used to estimate the occurrences of items within a data stream. CMS-CU stores m counters and employs d hash functions to map items to these counters. We first argue that the estimation error in CMS-CU is maximal when each item appears at most once in the stream. Next, we study CMS-CU in this setting. In the case where d=m-1, we prove that the average estimation error and the average counter rate converge almost surely to frac12, contrasting with the vanilla Count-Min Sketch, where the average counter rate is equal to fracm-1m. For any given m and d, we prove novel lower and upper bounds on the average estimation error, incorporating a positive integer parameter g. Larger values of this parameter improve the accuracy of the bounds. Moreover, the computation of each bound involves examining an ergodic Markov process with a state space of size binomm+g-dg and a sparse transition probabilities matrix containing O(mbinomm+g-dg) non-zero entries. For d=m-1, g=1, and as m→ ∞, we show that the lower and upper bounds coincide. In general, our bounds exhibit high accuracy for small values of g, as shown by numerical computation. For example, for m=50, d=4, and g=5, the difference between the lower and upper bounds is smaller than 10-4.