DOAJ Open Access 2012

Approximate Counting via the Poisson-Laplace-Mellin Method

Michael Fuchs Chung-Kuei Lee Helmut Prodinger

Lihat Sumber DOI

Abstrak

Approximate counting is an algorithm that provides a count of a huge number of objects within an error tolerance. The first detailed analysis of this algorithm was given by Flajolet. In this paper, we propose a new analysis via the Poisson-Laplace-Mellin approach, a method devised for analyzing shape parameters of digital search trees in a recent paper of Hwang et al. Our approach yields a different and more compact expression for the periodic function from the asymptotic expansion of the variance. We show directly that our expression coincides with the one obtained by Flajolet. Moreover, we apply our method to variations of approximate counting, too.

Topik & Kata Kunci

Mathematics

Penulis (3)

Michael Fuchs

Chung-Kuei Lee

Helmut Prodinger

Format Sitasi

APA MLA BibTeX

Fuchs, M., Lee, C., Prodinger, H. (2012). Approximate Counting via the Poisson-Laplace-Mellin Method. https://doi.org/10.46298/dmtcs.2980

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.2980

Informasi Jurnal

Tahun Terbit: 2012
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.2980
Akses: Open Access ✓