|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Approximate counting with a floating-point counter | | Miklos Csuros
; | | Date: |
20 Apr 2009 | | Abstract: | Robert Morris [{em Communications of the ACM}, 21:840--842, 1978] proposed a
probabilistic technique for approximate counting. 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$ events when
starting with X=1, and yields an unbiased estimator. Here we revisit the
original idea of Morris, and propose a binary floating-point counter for
tracking $n$. Namely, we use a $d$-bit significand in conjunction with a binary
exponent. The counter has a simple formula for an unbiased estimation of $n$
with a standard deviation of $O(n2^{-d/2})$. A floating-point counter matches
the accuracy of a base-$q$ Morris counter with $q=2^{2^{-d}}$ and uses the same
number of $d+lglg n$ bits. The floating-point counter has the advantage that
the incrementation probabilities are always integer powers of 1/2. As a
consequence, it needs $2nigl(1-o(1)igr)$ random bits on average in order to
count items in a data set of length $n$. Furthermore, the floating-point
counter tracks small values exactly until $n=2^d$. | | Source: | arXiv, 0904.3062 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER