Universal and Tight Bounds on Counting Errors of Count-Min Sketch with Conservative Updates
Younes Ben Mazziane, Othmane Marfoq · Proceedings of the ACM on Measurement and Analysis of Computing Systems · 2025
Count-Min Sketch with Conservative Updates ( CMS-CU ) is a memory-efficient hash-based algorithm used to estimate the occurrences of items within a data stream. CMS-CU employs d hash functions and a total of m counters arranged in d rows, with each hash function mapping an item to one counter per row. In this paper, we study a similar algorithm, which we refer to as CU-S, where d hash functions map each item to d distinct counters in a single array of size m . Specifically, we present an analytical method to quantify the trade-off between memory usage and the Counting Error ( CE ) of an item in CU-S, defined as the discrepancy between the estimated and actual number of its occurrences. The first result of this paper shows that items absent from the stream experience the highest CE. We refer to their error as the Unseen items Error ( UE ). The second result is an upper bound on UE of any stream, expressed in terms of the Reference Error ( RE ), which is UE of a reference stream where each item appears at most once. We also identify streams for which this bound is provably tight. The direct computation of RE involves dealing with an infinite state space Markov process similar to the Balls and Bins model with the Power of Choice, but more difficult to handle analytically. Instead, we construct two finite state space Markov processes, parametrized by a positive integer g , that bound the original chain and yield efficiently computable lower and upper bounds on RE. Increasing g narrows the gap between these bounds and enlarges the state space to ((m+g-d)/g), thus increasing the computation time. For d = m -1, g =1, and as m → ∞, we prove that the lower and upper bounds coincide. Our bounds are accurate for small values of g and for more general values of m and d , as shown by numerical computation. Finally, simulations on various streams confirm that bounding RE in this manner enables efficient and accurate computation of UE.