We are glad to present you an article written by Qrator Labs' engineer Dmitry Kamaldinov. If you want to be a part of our Core team, write us at firstname.lastname@example.org.
On implementing streaming algorithms, counting of events often occurs, where an event means something like a packet arrival or a connection establishment. Since the number of events is large, the available memory can become a bottleneck: an ordinary -bit counter allows to take into account no more than events.
One way to handle a larger range of values using the same amount of memory would be approximate counting. This article provides an overview of the well-known Morris algorithm and some generalizations of it.
Another way to reduce the number of bits required for counting mass events is to use decay. We discuss such an approach here , and we are going to publish another blog post on this particular topic shortly.
In the beginning of this article, we analyse one straightforward probabilistic calculation algorithm and highlight its shortcomings (Section 2). Then (Section 3), we describe the algorithm proposed by Robert Morris in 1978 and indicate its most essential properties and advantages. For most non-trivial formulas and statements, the text contains our proofs, the demanding reader can find them in the inserts. In the following three sections, we outline valuable extensions of the classic algorithm: you can learn what Morris's counters and exponential decay have in common, how to improve the accuracy by sacrificing the maximum value, and how to handle weighted events efficiently.
2 Probabilistic Counting, problems of the trivial approach
The main idea of probabilistic counting is taking into account the next event with a certain probability. Let us first consider an example with a constant update rate:
Where denotes the counter value after the th update attempt. It is easy to see that gives the number of successes among nn independent Bernoulli trials. In other words, has a binomial distribution:
The problem we are to solve is to estimate the actual number of events given only the random value obtained accordingly to the described update rule. It is natural to use as an estimator, since we know on average.
The described approach has several drawbacks: first, it allows to count up to times larger numbers comparing to the ordinary incremental counter, which is still noticeably less than, as we will see below, we get with Morris's counters. Second, the relative error is high for small . For example, if it is up to 100%. The coefficient of variation can estimate the relative error:
3 Morris's counters
The Morris's counter updates with a probability dependent on the current value: the first update occurs with a probability of 1, the next with 1/2, then 1/4, etc.:
How to estimate the number of events by the current counter value? Updating the counter from to occurs on average after iterations, hence a reasonable estimator would be
The most important properties of this estimator are the following:
it is unbiased, that is, the estimate after nn updates is on average ,
At the very beginning, the counter value is 0: then , so . Finally, .
and its relative error is independent of .
First, let's calculate the variance of . According to the well-known formula, . We already know . It remains to get . Notice, that
So, we are only to find .
And also, we can bound tail probabilities by Chebyshev's inequality:
Thus, the relative error of the number of events estimate is bounded, approximately constant and almost independent of .
If we are restricted with bits of memory, the event number range we can cover is . In other words, bits are sufficient to account up to events!
4 Weighted updates
Morris's counters can be used to count weighted events: for example, to sum up the sizes of incoming packets. The simplest way — updating the counter <event weight> times — leads the update complexity to be linear in weight.
Note that at each moment, we know how the number of update failures before the subsequent success is distributed; this is the geometric distribution:
Given this fact, we can speed up the algorithm by immediately skipping all consecutive unsuccessful update attempts:
There is often a need to take into account the most recent events with a higher priority. For instance, when looking for intensive keys in a stream, we might be more interested in detecting keys intense right now, rather than ones having a high average intensity due to the events in the past. In the article , we discussed the decay counters explicitly designed for this purpose. Another prerequisite for some form of decay is that despite the super-economical use of memory, even Morris's counters once may overflow. Fortunately, it turns out Morris's counters can also decay, moreover, it is very similar to EMA but much more efficient.
The basic idea is quite simple: we periodically subtract from the counter. Recall the counter value of estimates the number of events as .
Accordingly, after subtracting the estimate becomes .
In other words, subtracting decreases the estimate by a factor of ! We can achieve exactly times decrease by updating the counter with probability immediately after subtracting :
6 Mantissa and exponent
Consider the following generalization of Morris's counters: the probability of an update is halved not on every successful update, but on every updates. One possible implementation of this approach would be splitting the counter bits into two parts: exponential, responsible for the probability, and significand, counting the number of successful updates within the current probability (the notions are taken from floating point arithmetic).
Let us introduce the notation for the exponential and significand parts:
Now the update rule and the estimator of the number of events are written as follows:
For example, on figure 2 counter value is , the mantissa and exponent are equal to and correspondingly. So the event number estimate is .
With such a partition, the bits of the exponent are responsible for the covered range of the number of events, and the bits of the mantissa determine the accuracy of the estimate (these claims are described in detail below). The best partition of the counter bits depends on the application; we suggest giving as many bits to the mantissa as possible, but with enough exponential bits to cover the target value range.
The described variant of Morris's counters has the following properties:
the covered range of values is
The covered range is easy to get by substituting the maximum possible values and into the estimator :
a new estimator is also unbiased: ;
Similarly to the proof of the statement for the ordinary Morris's counters, we calculate the conditional expectation . And we will do it separately for (the probability of the update changes on success) and .
In both cases
the coefficient of variation (and the relative error) gets even smaller! We do not know its exact value, but there is a bound:
(recall the analogous value for classic Morris's counter is )
Weighted update and decay algorithms will also change slightly.
Similarly to the approach described in Section 4, to perform a weighted update efficiently, we are to figure out how many update attempts are needed to change the probability. Formerly, without the mantissa, the probability changes on each successful update, but now it changes after every updates. So we need the distribution of the number of Bernoulli trials (the required number of events), among which there are precisely successful ones. This distribution is called negative binomial.
Remark. Actually, there are several definitions of the negative binomial distribution. We will use the one that claims it as a distribution of the number of failures with a given number of successes. Then, to get the number of events, we need to add the number of successes to the random value:
In order to avoid generating the negative binomial distribution, one can simplify the algorithm by just using the mean of this distribution:
To perform the decay, we subtract from the exponential part (in other words, from the counter value). Then
Note that for (namely, this case is studied in this section) . Therefore, the estimate can be corrected by updating by :
Morris's counters are awesome! Use them!
The last section does not contain practical results, but ...
8 Generalized Probabilistic Counters
In general, the rule for updating the counter is determined by the probability function :
In the case of Morris's counters . When studying probabilistic counters, we tried to take a linear probability function: ( — some constant, the upper bound of the counter).
This had led to some interesting results, which are summarized in this section.
Before presenting these results, let us recall two mathematical entities. A complete symmetric homogeneous polynomial of degree in variables is the sum of all possible monomials of degree in these variables with coefficients :
Another construction that we need is the Stirling number of the second kind. One of the ways to define this number is combinatorial: the Stirling number of the second kind is the number of partitions of the nn-element set into mm non-empty subsets. Stirling numbers are associated with complete symmetric homogeneous polynomials:
With the help of , we can write in general form the probability of counter value after updates being equal to
This formula is easy to prove by induction. However, it can also be deduced from simple combinatorial reasoning: in fact, it says that in order to get the value of , successful updates are needed: from to , from to , and etc., — the factor stands for this;
and unsuccessful, which can be logically divided into groups: failed updates from to , from to , and so on, which is expressed as .
Finally, when using the linear probability function , the probability takes the form
That is the exciting result announced above. We noticed the Stirling number in the probability value quite accidentally and still do not know whether it is possible to justify its presence by combinatorial reasoning (relying on its combinatorial definition). One another question is whether there is also a nice formula for in the case of Morris's counters.
The expected value and variance of (we omit the proofs since this type of counters is not the main subject of this article, but they simply follow from the properties of the Stirling numbers and the equation for ):
The number of events can be estimated using the method of moments:
or similarly to Morris's counters, taking into account that :
 Morris, R.Counting large numbers of events in small registers Communications of the ACM, 1978 21(10), 840-842.
 http://gregorygundersen.com/blog/2019/11/11/morris-algorithm/ − an overview of Morris’s counters
 https://qratorlabs.medium.com/rate-detector-21d12567d0b5 − our article about EMA counters