A formal analysis of conservative update based approximate counting
Gil Einziger, Roy Friedman · 2015 International Conference on Computing, Networking and Communications (ICNC) · 2015
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.