Approximate counting algorithm
 | 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 |
| 10 | 2 | 2 or more |
| 11 | 4 | 3 or more |
| 100 | 8 | 4 or more |
| 101 | 16 | 5 or more |
| 110 | 32 | 6 or more |
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]