{"id":389488,"date":"2024-06-29T08:37:44","date_gmt":"2024-06-29T08:37:44","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=389488"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=389488","title":{"rendered":"Overview of Morris’s counters<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n
\"An
An artist’s concept showing counting of elements in a stream with limited resources<\/figcaption><\/figure>\n

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\u00a0<\/sub>hr@qrator.net<\/sub><\/a>.<\/sub><\/p>\n

1 Introduction<\/h3>\n

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\u00a0\"n\"-bit counter allows to take into account no more than\u00a0\"2^nevents.
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.<\/p>\n

Another way to reduce the number of bits required for counting mass events is to use decay. We discuss such an approach\u00a0here<\/a>\u00a0[3], and we are going to publish another blog post on this particular topic shortly.<\/p>\n

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.<\/p>\n

2 Probabilistic Counting, problems of the trivial approach<\/h3>\n

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:<\/p>\n

\"\\begin{equation*}<\/p>\n

Where\u00a0\"C_n\"denotes the counter value after the\u00a0\"n\"th update attempt. It is easy to see that\u00a0\"C_n\"gives the number of successes among\u00a0nn\u00a0independent Bernoulli trials. In other words,\u00a0\"C_n\"has a\u00a0binomial distribution<\/a>: <\/p>\n

\"\\begin{align*}<\/p>\n

The problem we are to solve is to estimate the actual number of events \"n\"given only the random value \"C_n\"obtained accordingly to the described update rule. It is natural to use \"\\widehat{n}(C)as an estimator, since we know \"C_non average.<\/p>\n

The described approach has several drawbacks: first, it allows to count up to \"1\/ptimes 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<\/em> is high for small \"n\". For example, if \"nit is up to 100%. The coefficient of variation can estimate the relative error:<\/p>\n

\"\\begin{align*}<\/p>\n

3\u00a0Morris’s counters<\/h3>\n

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.:<\/p>\n

\"\\begin{equation*}<\/p>\n

How to estimate the number of events by the current counter value? Updating the counter from \"x\"to \"xoccurs on average after \"2^x\"iterations, hence a reasonable estimator would be<\/p>\n

\"\\widehat{n}(C)<\/p>\n

The most important properties of this estimator are the following:<\/p>\n