×

Approximate counting: a detailed analysis. (English) Zbl 0562.68027

Approximate counting is a probabilistic algorithm proposed by R. Morris [Commun. ACM 21, 840-842 (1978; Zbl 0386.68035)] that allows the storage of (many) large counts in small counters. The algorithm allows counting up to some integer n in space \(\approx \log_ 2\log_ 2n+\delta\) with a constant expected relative accuracy that is \(O(2^{- \delta /2})\). For instance, using only 8 bits, one can count up to \(2^{16}=65536\) with an accuracy of about 15 %. The paper presents a complete analysis of the algorithm which is equivalent to a pure birth process with discrete time and birth probabilities of the form \(2^{- k}\). The probability distribution of the approximate result is characterized exactly and is also shown to tend to a limiting distribution. Mean and variance of the result are estimated asymptotically using a combination of: (i) combinatorial identities in the theory of integer partitions; (2) Mellin transform techniques. The paper concludes with a comparison of approximate counting with direct sampling methods. One should also note that related methods appear in the space-efficient simulation of deterministic machines by probabilistic machines (Freivalds, Gill).

MSC:

68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
68N25 Theory of operating systems

Citations:

Zbl 0386.68035
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Comtel,L’Analyse Combinatoire, 2 vol., P.U.F., Paris (1970).
[2] G. Doetsch,Handbuch der Laplace Transformation, Birkhauser Verlag, Basel (1955). · Zbl 0065.34001
[3] P. Flajolet and N. Martin,Probabilistic counting, in Proc. 24th Annual Symp. on Foundations of Comp. Sc., Tucson, Arizona (1984), pp. 76–82.
[4] R. G. Gallager,Variations on a theme by Huffmann, IEEE Trans. IT, 24 (1978) pp. 669–674. · Zbl 0399.94012 · doi:10.1109/TIT.1978.1055959
[5] L. Kleinrock,Queuing Systems, Wiley Interscience, New York (1976). · Zbl 0361.60082
[6] D. E. Knuth,The Art of Computer Programming: Sorting and Searching, Addison-Wesley, Reading (1973). · Zbl 0302.68010
[7] G. Langdon and J. Rissanen,Compression of black white images with binary arithmetic coding, IEEE Trans. on Communications (1981). · Zbl 0456.94009
[8] R. Morris,Counting large numbers of events in small registers, Comm. ACM, 21 (1978), pp. 840–842. · Zbl 0386.68035 · doi:10.1145/359619.359627
[9] S. Todd, N. Martin, G. Langdon and D. Helman,Dynamic statistics collection for compression coding, Unpublished manuscript, 12 p. (1981).
[10] E. T. Whittaker and G. N. Watson,A Course in Modern Analysis, (1907); 4th edition, Cambridge Univ. Press, 1927. · JFM 45.0433.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.