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.
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.
There is a fairly low probability that the actual count of increment events was 5 (
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.
As the result was zero if any of those pseudo-random bits are zero, achieving an increment probability of
This procedure is executed each time the request is made to increment the counter.
The algorithm is useful in examining large data streams for patterns.