Approximate counting algorithm: Difference between revisions
(No difference)
| |
Revision as of 21:24, 8 November 2008
 | This article, Approximate counting algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: |
The Approximate counting algorithm allows you to count a large number of events using a small amount of memory. Invented in 1997 by Robert Morris of Bell Labs, it uses probabilistic techniques to increment the counter.
Theory of Operation
Using Morris' algorithm, the counter represents an "order of magnitude estimate" of the actual count. The approximation is mathematically unbiased.
In order to increment the counter, a pseudo-random event is used, such that the incrementing is a probabilistic event. In order to save space, only the exponent is kept. For example, in base 2, the counter can estimate the count to be 1, 2, 4, 8, 16, 32, and all of the powers of two. The memory requirement is simply to hold the exponent.
In order to increment from say 4 to 8, a pseudo-random number would be generated such that a probability of .25 generates a positive change in the counter. Otherwise, the counter remains at 4.
Here is a table of potential values:
| Stored Binary Value | Approximation | Possible range of actual counts |
|---|---|---|
| 0 | 1 | exactly 1 |
| 1 | 2 | 2 or more |
| 10 | 4 | 3 or more |
| 11 | 8 | 4 or more |
| 100 | 16 | 5 or more |
| 101 | 32 | 6 or more |
Algorithm
When incrementing the counter, simply "flip a coin" the number of times of the counter's current value. If it comes up "Heads" each time, then increment the counter. Otherwise, do not increment it.
This can be done programmatically by generating "c" pseudo-random bits (where "c" is the current value of the counter), and using the logical AND function on all of those bits. The result is a zero if any of those pseudo-random bits were zero, and a one if they were all ones. Simply add the result to the counter. This procedure should be executed each time the request is made to increment the counter.
Applications
The algorithm is useful in examining large data streams for patterns. This is particularly useful in applications of data compression, sight and sound recognition, and other artificial intelligence applications.
Sources
Morris, R. Counting large numbers of events in small registers. Communications of the ACM 21, 10 (1977), 840–842
Flajolet, P. Approximate Counting: A Detailed Analysis. BIT 25, (1985), 113-134 [1]