BibTex RIS Cite

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

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.

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

Guy Louchard Helmut Prodinger

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

Abstract

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.
There are 15 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

Guy Louchard This is me

Helmut Prodinger This is me

Publication Date September 14, 2015
Published in Issue Year 2015 Volume: 2 Issue: 3

Cite

APA Louchard, G., & Prodinger, H. (2015). Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(3), 191-209. https://doi.org/10.13069/jacodesmath.36015
AMA Louchard G, Prodinger H. Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications. September 2015;2(3):191-209. doi:10.13069/jacodesmath.36015
Chicago Louchard, Guy, and Helmut Prodinger. “Approximate Counting With M Counters: A Probabilistic Analysis”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, no. 3 (September 2015): 191-209. https://doi.org/10.13069/jacodesmath.36015.
EndNote Louchard G, Prodinger H (September 1, 2015) Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications 2 3 191–209.
IEEE G. Louchard and H. Prodinger, “Approximate counting with m counters: A probabilistic analysis”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 3, pp. 191–209, 2015, doi: 10.13069/jacodesmath.36015.
ISNAD Louchard, Guy - Prodinger, Helmut. “Approximate Counting With M Counters: A Probabilistic Analysis”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/3 (September 2015), 191-209. https://doi.org/10.13069/jacodesmath.36015.
JAMA Louchard G, Prodinger H. Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:191–209.
MLA Louchard, Guy and Helmut Prodinger. “Approximate Counting With M Counters: A Probabilistic Analysis”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 3, 2015, pp. 191-09, doi:10.13069/jacodesmath.36015.
Vancouver Louchard G, Prodinger H. Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(3):191-209.