Marianne Durand: A Probabilistic Counting Algorithm

Probabilistic counting algorithms estimate approximately the number of different words in a very large collection of data in a single pass using a very small memory. We consider a modification of the Probabilistic Counting algorithm of Flajolet and Martin [FM85]. This is based on the observation of occurrences of initial sequences of $0$'s in the binary representation of the words. The precision obtained is around $3\%$ for a memory requirement of 10kbits. The analysis involves maxima of geometric random variables and Mellin transform techniques.


Christian Estan and George Varghese.
Counting active flows in high-speed routers.
manuscript, 2002.

Philippe Flajolet and G. Nigel Martin.
Probabilistic counting algorithms for data base applications.
J. Comput. System Sci., 31(2):182-209, 1985.
Special issue: Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983).

Back to the Index

Please send comments and corrections to Thomas Klausner.