Approximate counting with m counters: A probabilistic analysis
Keywords:
Approximate counting, Moments, Constant and fluctuating components, Complex analysis, Product of Fourier seriesAbstract
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].
Downloads
References
J. Cichoń and W. Macyna, Approximate counters for flash memory, in 2011 IEEE 17th International Conference on Embedded and Real-Time Computing Systems and Applications, Toyama, Japan (2011) 238-242.
P. Flajolet, Approximate counting: A detailed analysis, BIT 25(4) (1985) 113-134.
P. Flajolet and R. Sedgewick, Digital search trees revisited, SIAM J. Comput. 15(3) (1986) 748-767.
M. Fuchs, C.-K. Lee, and H. Prodinger, Approximate counting via the Poisson-Laplace-Mellin method, Discrete Math. Theor. Comput. Sci. Proc. AQ (2012) 13-28.
H.-K. Hwang, M. Fuchs, and V. Zacharovas, Asymptotic variance of random symmetric digital search trees, Discrete Math. Theor. Comput. Sci. 12(2) (2010) 103-166.
P. Kirschenhofer and H. Prodinger, Approximate counting: An alternative approach, RAIRO Inform. Théor. Appl. 25(1) (1991) 43-48.
D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, Reading, MA (1973), Second edition (1998).
M. Loève, Probability Theory, 3rd edition, D. Van Nostrand, Princeton, NJ (1963).
G. Louchard, Exact and asymptotic distributions in digital and binary search trees, RAIRO Inform. Théor. Appl. 21(4) (1987) 479-496.
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(3-4) (2006) 431-467.
G. Louchard and H. Prodinger, Generalized approximate counting revisited, Theoret. Comput. Sci. 391(1-2) (2008) 109-125.
H. Prodinger, Hypothetic analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet, Theoret. Comput. Sci. 100(1) (1992) 243-251.
H. Prodinger, Approximate counting via Euler transform, Math. Slovaca 44(5) (1994) 569-574.
H. Prodinger, Periodic oscillations in the analysis of algorithms and their cancellations, J. Iranian Stat. Soc. 3(2) (2004) 251-270.
H. Prodinger, Approximate counting with $m$ counters: A detailed analysis, Theoret. Comput. Sci. 439 (2012) 58-68.
