The approximate counting algorithm allows the counting of a large number of events using a small amount of memory. Invented in 1977 by Robert Morris of Bell Labs, it uses probabilistic techniques to increment the counter. It was fully analyzed in the early 1980s by Philippe Flajolet of INRIA Rocquencourt, who coined the name approximate counting, and strongly contributed to its recognition among the research community. When focused on high quality of approximation and low probability of failure, Nelson and Yu showed that a very slight modification to the Morris Counter is asymptotically optimal amongst all algorithms for the problem.[1] The algorithm is considered one of the precursors of streaming algorithms, and the more general problem of determining the frequency moments of a data stream has been central to the field.
Using Morris' algorithm, the counter represents an "order of magnitude estimate" of the actual count. The approximation is mathematically unbiased.
To increment the counter, a pseudo-random event is used, such that the incrementing is a probabilistic event. 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.
As an example, to increment from 4 to 8, a pseudo-random number would be generated such that the probability the counter is increased is 0.25. Otherwise, the counter remains at 4.
The table below illustrates some of the potential values of the counter:
| Stored binary value of counter | Approximation | Range of possible values for the actual count | Expectation (sufficiently large n, uniform distribution) | |
|---|---|---|---|---|
| 0 | 1 | 0, or initial value | 0 | |
| 1 | 2 | 1 or more | 2 | |
| 10 | 4 | 2 or more | 6 | |
| 11 | 8 | 3 or more | 14 | |
| 100 | 16 | 4 or more | 30 | |
| 101 | 32 | 5 or more | 62 |
If the counter holds the value of 101, which equates to an exponent of 5 (the decimal equivalent of 101), then the estimated count is
25
| 1 | |
| 1024 |
=1 x
| 1 | |
| 2 |
x
| 1 | |
| 4 |
x
| 1 | |
| 8 |
x
| 1 | |
| 16 |
While using powers of 2 as counter values is memory efficient, arbitrary values tend to create a dynamic error range, and the smaller values will have a greater error ratio than bigger values. Other methods of selecting counter values consider parameters such as memory availability, desired error ratio, or counting range to provide an optimal set of values.[2]
However, when several counters share the same values, values are optimized according to the counter with the largest counting range, and produce sub-optimal accuracy for smaller counters. Mitigation is achieved by maintaining Independent Counter Estimation buckets,[3] which restrict the effect of a larger counter to the other counters in the bucket.
The algorithm can be implemented by hand. When incrementing the counter, flip a coin a number of times corresponding to the counter's current value. If it comes up heads each time, then increment the counter. Otherwise, do not increment it.
This can be easily achieved on a computer. Let
c
c
2-c
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.