TLDR: Space-Efficient Counting - Exploring Morris' Algorithm

Date: 2020-08-02 Source: https://arpitbhayani.me/blogs/morris-counter

Overview

Learn about the Morris Algorithm, a probabilistic method for counting large events with minimal memory. Explore its math and implementation. Approximate Counting algorithms are techniques that allow us to count a large number of events using a very small amount of memory.

Key Points

• Approximate Counting algorithms are techniques that allow us to count a large number of events using a very small amount of memory.
• Incrementing the value: Since we are building a counter, all we know is the value of the counter v and have no knowledge of the actual number of events seen.
• It was invented by Robert Morris in 1977 and was published through his paper Counting large number of events in small registers.
• The algorithm uses probabilistic techniques to increment the counter, although it does not guarantee the exactness it does provide a fairly good estimate of the true value while inducing a minimal and yet fairly constant relative error.