Approximate Counting Algorithm - Theory of Operation

Theory of Operation

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 a probability of .25 generates a positive change in the counter. 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
0 1 0, or initial value
1 2 1 or more
10 4 2 or more
11 8 3 or more
100 16 4 or more
101 32 5 or more

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 2^5, or 32. There is a very low probability that the actual count of increment events was 5 (which would imply that an extremely rare event occurred with the pseudo-random number generator, the same probability as getting 10 consecutive heads in 10 coin flips). The actual count of increment events is likely to be around 32, but it could be infinitely high (with decreasing probabilities for actual counts above 32).

Read more about this topic:  Approximate Counting Algorithm

Other articles related to "theory of operation":

Theory Of Operation

A theory of operation is a description of how a device or system should work. It is often included in documentation, especially maintenance/service documentation, or a user manual. It aids troubleshooting by providing the troubleshooter with a mental model of how the system is supposed to work. The troubleshooter can then more easily identify discrepancies, to aid diagnosis of problem.

IBM Redbooks are "Theories of operation" of their products.

Famous quotes containing the words theory of, operation and/or theory:

    Hygiene is the corruption of medicine by morality. It is impossible to find a hygienest who does not debase his theory of the healthful with a theory of the virtuous.... The true aim of medicine is not to make men virtuous; it is to safeguard and rescue them from the consequences of their vices.
    —H.L. (Henry Lewis)

    It requires a surgical operation to get a joke well into a Scotch understanding. The only idea of wit, or rather that inferior variety of the electric talent which prevails occasionally in the North, and which, under the name of “Wut,” is so infinitely distressing to people of good taste, is laughing immoderately at stated intervals.
    Sydney Smith (1771–1845)

    Many people have an oversimplified picture of bonding that could be called the “epoxy” theory of relationships...if you don’t get properly “glued” to your babies at exactly the right time, which only occurs very soon after birth, then you will have missed your chance.
    Pamela Patrick Novotny (20th century)