A formal analysis of conservative update based approximate counting
A formal analysis of conservative update based approximate counting
复制标题
DOI：
10.1109/iccnc.2015.7069350
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Gil Einziger;R. Friedman
中科院分区：
文献类型：
--
作者：
Gil Einziger;R. Friedman
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.
