Optimal bounds for approximate counting
share
Storing a counter incremented N times would naively consume O(log N) bits of memory. In 1978 Morris described the very first streaming algorithm: the "Morris Counter" [Morris78]. His algorithm has been shown to use O(loglog N + log(1/ε) + log(1/δ)) bits of memory to provide a (1+ε)-approximation with probability 1-δ to the counter's value. We provide a new simple algorithm with a simple analysis showing that O(loglog N + log(1/ε) + loglog(1/δ)) bits suffice for the same task, i.e. an exponentially improved dependence on the inverse failure probability. We then provide a more technical analysis showing that the original Morris Counter itself, after a minor but necessary tweak, actually also enjoys this same improved upper bound. Lastly, we prove a new lower bound for this task showing optimality of our upper bound. We thus completely resolve the asymptotic space complexity of approximate counting.
READ FULL TEXT