A Deep Analysis on General Approximate Counters

摘要

Approximate counters play an important role in many computer domains like network measurement, parallel computing and machine learning because they can reduce the required memory cost. With the emergence of new application needs in these domains like flow counting and parallel measuring, simple Morris counters fail to solve them. Therefore, a more general Morris counter is required. However, there has been a lack of complete theoretical research on the statistical properties of this new approximate counter so far.This paper conducts a deep analysis on general Morris counters and derives the minimum upper bound of the variance. To our best knowledge, this is the first work to thoroughly analyze the statistical properties of general Morris counters in theory. Besides, application scenarios are analyzed, showing that conclusions obtained by our research are effective in testing the performance of approximate counters and guiding system architecture design according to accuracy needs.