An algorithm for approximate counting using limited memory resources
Andrej Cvetkovski · 2007
This paper describes a randomized algorithm for approximate counting that preserves the same modest memory requirements of log(log n) bits per counter as the approximate counting algorithm introduced in the seminal paper of R. Morris (1978), and in addition, is characterized by (i) lower expected number of memory accesses and (ii) lower standard error on more than 99 percent of its counting range. An exact analysis of the relevant statistical properties of the algorithm is carried out. Performance evaluation via simulations is also provided to validate the presented theory.