Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Approximate Counting via the Poisson-Laplace-Mellin Method

Abstract : 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.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, September 11, 2015 - 12:55:00 PM
Last modification on : Tuesday, March 7, 2017 - 3:18:32 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:35:03 AM


Publisher files allowed on an open archive




Michael Fuchs, Chung-Kuei Lee, Helmut Prodinger. Approximate Counting via the Poisson-Laplace-Mellin Method. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.13-28, ⟨10.46298/dmtcs.2980⟩. ⟨hal-01197238⟩



Record views


Files downloads