At work we do a lot of counting. For some counts we need an accurate result, while for others we can get by with an approximate count. For these approximate counts, as long as the result is within the same order of magnitude of the true count, we're ok.
There is a lot of literature on approximate counting techniques, and the blog post "Probabilistic Data Structures for Web Analytics and Data Mining" does a great job at explaining some of them in detail, with references to the original papers.
There is a lot of literature on approximate counting techniques, and the blog post "Probabilistic Data Structures for Web Analytics and Data Mining" does a great job at explaining some of them in detail, with references to the original papers.
One of the original approximate counting papers was the 1978 paper: Counting large numbers of events in small registers by Robert Morris. In the paper Morris explains the context for the problem, which might seem foreign today. Back in 1978 he was faced with the problem of counting a large number of different events, and because of memory restrictions he could only use 8-bit registers for each counter. Since he was not interested in exact counts, but with accurate enough counts, he came with the technique of probabilistic counting.
The first solution he explored in the paper was to count every other event based on a flip of a coin. If the probability of the coin flip is $p$, for a true value $n$, the expected value of the counter is $n/2$, with a standard deviation of $\sqrt{n/4}$. The error for such a solution is high for small values of $n$.
Morris then presents his second solution, by introducing a counter that stores the logarithm of the number of events that have occurred $v$, and not the raw count of the events. He increments the counter value $v$ probabilistically based on a flip of a coin. The stored value in the counter is $\log{1+n}$ and the probability of increasing the counter is $1/\Delta = \exp{(v+1)}-\exp{(v)}$.
The paper is an enjoyable short read, and it is amazing that the techniques introduced in the 70's are still applicable to technology problems today.
The first solution he explored in the paper was to count every other event based on a flip of a coin. If the probability of the coin flip is $p$, for a true value $n$, the expected value of the counter is $n/2$, with a standard deviation of $\sqrt{n/4}$. The error for such a solution is high for small values of $n$.
Morris then presents his second solution, by introducing a counter that stores the logarithm of the number of events that have occurred $v$, and not the raw count of the events. He increments the counter value $v$ probabilistically based on a flip of a coin. The stored value in the counter is $\log{1+n}$ and the probability of increasing the counter is $1/\Delta = \exp{(v+1)}-\exp{(v)}$.
The paper is an enjoyable short read, and it is amazing that the techniques introduced in the 70's are still applicable to technology problems today.
Comments
Post a Comment