Gil Einziger

This paper presents a formal analysis of multiple popular approximate counting schemes that employ the conservative update policy, such as CU-Sketch and Minimal Increment Spectral Bloom Filters, under a unified framework. It is also shown that when applied to items picked from a skewed distribution, such as Zipf-like functions, the analysis follows very closely empirical results obtained through simulations. Furthermore, this paper's analysis is orders of magnitude more accurate than previously known analysis of approximate counting schemes.