Multi-dimensional Approximate Counting

Dingyu Wang

The celebrated Morris counter uses ${\log }_2{\log }_{2}n+O({\log }_2{\sigma }^{-1})$ bits to count up to $n$ with a relative error $\sigma$, where if $\hat{\lambda }$ is the estimate of the current count $\lambda$,…