Count-Min Sketch with Variable Number of Hash Functions: An Experimental Study

International audienceConservative Count-Min, a stronger version of the popular Count-Min sketch [Cormode, Muthukrishnan 2005], is an online-maintained hashing-based sketch summarizing element frequency information of a stream. Although several works attempted to analyze the error of conservative Count-Min, its behavior remains poorly understood. In [Fusy, Kucherov 2022], we demonstrated that under the uniform distribution of input elements, the error of conservative Count-Min follows two distinct regimes depending on its load factor.In this work, we present a series of results providing new insights into the behavior of conservative Count-Min. Our contribution is twofold. On one hand, we provide a detailed experimental analysis of Count-Min sketch in different regimes and under several representative probability distributions of input elements. On the other hand, we demonstrate improvements that can be made by assigning a variable number of hash functions to different elements. This includes, in particular, reduced space of the data structure while still supporting a small error