Approximate counting with a floating-point counter

Details Approximate counting with a floating-point counter Approximate counting with a floating-point counter

2009-04-20

arxiv.org/abs/0904.3062v2

Computer Science

Data Structures and Algorithms

Updated content (fixed errors in the previous version)

Scientific paper

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\cdot 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.

Affiliated with

Also associated with

No associations

Rating

Approximate counting with a floating-point counter does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate counting with a floating-point counter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate counting with a floating-point counter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-174335