2009/04/20 by Miklos Csuros, Csuros, Miklos
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.0904.3062
Updated content (fixed errors in the previous version)
openalex publication_date 2009/04/20 · arxiv created 2009/08/24 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Memory becomes a limiting factor in contemporary applications, such as analyses of the Webgraph and molecular sequences, when many objects need to be counted simultaneously. Robert Morris [Communications of the ACM, 21:840--842, 1978] proposed a probabilistic technique for approximate counting that is extremely space-efficient. The basic idea is to increment a counter containing the value X with probability 2-X. As a result, the counter contains an approximation of \lg n after n probabilistic updates stored in \lg\lg n bits. Here we revisit the original idea of Morris, and introduce a binary floating-point counter that uses a d-bit significand in conjunction with a binary exponent. The counter yields a simple formula for an unbiased estimation of n with a standard deviation of about 0.6⋅ n2-d/2, and uses d+\lg\lg n bits. We analyze the floating-point counter's performance in a general framework that applies to any probabilistic counter, and derive practical formulas to assess its accuracy.