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

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 1/2, contrasting with the vanilla Count-Min Sketch, where the average counter rate is equal to m-1/m. 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 m+g-dg and a sparse transition probabilities matrix containing O(mm+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⁻⁴.