Universal and Tight Bounds on Counting Errors of Count-Min Sketch with Conservative Updates

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. In this paper, we study a similar algorithm, which we refer to as CU-S, where d hash functions map each item to d 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. Finally, we construct two Markov processes parametrized by g which yield lower and upper bounds on RE, with g balancing accuracy and computation time of these bounds.