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 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.