Approximate counting with m counters: A probabilistic analysis

Year 2015, Volume: 2 Issue: 3, 191 - 209, 14.09.2015

Guy Louchard Helmut Prodinger

https://doi.org/10.13069/jacodesmath.36015

https://izlik.org/JA77CT98MM

Abstract

Motivated by a recent paper by Cicho\'n and Macyna [1], who introduced $m$ counters (instead of just one) in the approximate counting scheme first analysed by Flajolet [2], we analyse the moments of the sum of the $m$ counters, using techniques that proved to be successful already in several other contexts [11].

Keywords

Approximate counting , Moments , Constant and fluctuating components , Complex analysis , Product ofFourier series

References

• J. Cichoń and W. Macyna, Approximate counters for flash memory, 17th IEEE International Confer- ence on Embedded and Real-Time Computing Systems and Applications (RTCSA), Toyama, Japan, 20 P. Flajolet, Approximate counting: A detailed analysis, BIT, 25, 113–134, 1985.
• P. Flajolet and R. Sedgewick, Digital search trees revisited, SIAM J. Comput., 3, 748–767, 1986.
• M. Fuchs, C. K. Lee, and H. Prodinger, Approximate counting via the Poisson-Laplace-Mellin method, DMTCS, proc AQ, 13–28, 2012.
• H.-K. Hwang, M. Fuchs and V. Zacharovas, Asymptotic variance of random symmetric digital search trees, Discrete Math. Theor. Comput. Sci., 12, 103–166, 2010.
• P. Kirschenhofer and H. Prodinger, Approximate counting: An alternative approach, RAIRO Theor. Inform. Appl., 25, 43–48, 1991.
• D. E. Knuth, The art of computer programming, volume 3: Sorting and searching, Addison-Wesley, 1973, (Second edition, 1998).
• M. Loève, Probability theory, 3rd ed, D. Van Nostrand, 1963.
• G. Louchard, Exact and asymptotic distributions in digital and binary search trees, RAIRO Theor. Inform. Appl., 21(4), 479–496, 1987.
• G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Technical report, 2005. Long version: http://www.ulb.ac.be/di/mcs/louchard/moml.ps.
• G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Algorithmica, 46, 431–467, 2006.
• G. Louchard and H. Prodinger, Generalized approximate counting revisited, Theoret. Comput. Sci., 391, 109–125, 2008.
• H. Prodinger, Hypothetic analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet, Theoret. Comput. Sci., 100, 243–251, 1992.
• H. Prodinger, Approximate counting via Euler transform, Mathematica Slovaka, 44, 569–574, 1994.
• H. Prodinger, Periodic oscillations in the analysis of algorithms and their cancellations, J. Iran. Stat. Soc., 3, 251–270, 2004.
• H. Prodinger, Approximate counting with m counters: a detailed analysis, Theoret. Comput. Sci., 439, 58–68, 2012.