zbMATH — the first resource for mathematics

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
Full Text:
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 [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 [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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.