Approximate Counting via the Poisson-Laplace-Mellin Method
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 shap...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2012-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2980/pdf |
| _version_ | 1797270355001212928 |
|---|---|
| author | Michael Fuchs Chung-Kuei Lee Helmut Prodinger |
| author_facet | Michael Fuchs Chung-Kuei Lee Helmut Prodinger |
| author_sort | Michael Fuchs |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:02:57Z |
| format | Article |
| id | doaj.art-6e00ff6651b64941ae862d4055425246 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:57Z |
| publishDate | 2012-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-6e00ff6651b64941ae862d40554252462024-03-07T14:50:50ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502012-01-01DMTCS Proceedings vol. AQ,...Proceedings10.46298/dmtcs.29802980Approximate Counting via the Poisson-Laplace-Mellin MethodMichael Fuchs0Chung-Kuei Lee1Helmut Prodinger2Department of Applied Mathematics [Hsinchu]Department of Applied Mathematics [Hsinchu]Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]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.https://dmtcs.episciences.org/2980/pdfapproximate countingdigital search treejs-admissibilitylaplace transformmellin transform[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co][info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| spellingShingle | Michael Fuchs Chung-Kuei Lee Helmut Prodinger Approximate Counting via the Poisson-Laplace-Mellin Method Discrete Mathematics & Theoretical Computer Science approximate counting digital search tree js-admissibility laplace transform mellin transform [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| title | Approximate Counting via the Poisson-Laplace-Mellin Method |
| title_full | Approximate Counting via the Poisson-Laplace-Mellin Method |
| title_fullStr | Approximate Counting via the Poisson-Laplace-Mellin Method |
| title_full_unstemmed | Approximate Counting via the Poisson-Laplace-Mellin Method |
| title_short | Approximate Counting via the Poisson-Laplace-Mellin Method |
| title_sort | approximate counting via the poisson laplace mellin method |
| topic | approximate counting digital search tree js-admissibility laplace transform mellin transform [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| url | https://dmtcs.episciences.org/2980/pdf |
| work_keys_str_mv | AT michaelfuchs approximatecountingviathepoissonlaplacemellinmethod AT chungkueilee approximatecountingviathepoissonlaplacemellinmethod AT helmutprodinger approximatecountingviathepoissonlaplacemellinmethod |