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

Count-Min Sketch with Conservative Updates (\texttt{CMS-CU}) is a memory-efficient hash-based data structure used to estimate the occurrences of items within a data stream. \texttt{CMS-CU} stores~$m$ counters and employs~$d$ hash functions to map items to these counters. We first argue that the estimation error in \texttt{CMS-CU} is maximal when each item appears at most once in the stream. Next, we study \texttt{CMS-CU} in this setting. Precisely, \begin{enumerate} \item In the case where~$d=m-1$, we prove that the average estimation error and the average counter rate converge almost surely to~$\frac{1}{2}$, contrasting with the vanilla Count-Min Sketch, where the average counter rate is equal to~$\frac{m-1}{m}$. \item 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~$\binom{m+g-d}{g}$ and a sparse transition probabilities matrix containing~$\mathcal{O}(m\binom{m+g-d}{g})$ non-zero entries. \item For~$d=m-1$, $g=1$, and as $m\to \infty$, 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}$. \end{enumerate}