TY - GEN

T1 - Optimal Bounds for Approximate Counting

AU - Nelson, Jelani

AU - Yu, Huacheng

N1 - Funding Information:
J.N. was supported by NSF grant CCF-1951384, ONR grant N00014-18-1-2562, and ONR DORECG award N00014-17-1-2127.
Publisher Copyright:
© 2022 Owner/Author.

PY - 2022/6/12

Y1 - 2022/6/12

N2 - 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"[15]. His algorithm's space bound is a random variable, and it has been shown to be O(log log N + log(1/?) + log(1/)) bits in expectation to provide a (1+?)-Approximation with probability $1-dto the counter's value. We provide a new simple algorithm with a simple analysis showing that randomized space O(log log N + log(1/?) + log log(1/)) bits suffice for the same task, i.e. an exponentially improved dependence on the inverse failure probability. We then provide a new 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. Furthermore all our constants are explicit, and our lower bound and tightest upper bound differ by a multiplicative factor of at most 3+o(1).

AB - 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"[15]. His algorithm's space bound is a random variable, and it has been shown to be O(log log N + log(1/?) + log(1/)) bits in expectation to provide a (1+?)-Approximation with probability $1-dto the counter's value. We provide a new simple algorithm with a simple analysis showing that randomized space O(log log N + log(1/?) + log log(1/)) bits suffice for the same task, i.e. an exponentially improved dependence on the inverse failure probability. We then provide a new 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. Furthermore all our constants are explicit, and our lower bound and tightest upper bound differ by a multiplicative factor of at most 3+o(1).

KW - approximate counting

KW - lower bounds

KW - streaming

UR - http://www.scopus.com/inward/record.url?scp=85133025093&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85133025093&partnerID=8YFLogxK

U2 - 10.1145/3517804.3526225

DO - 10.1145/3517804.3526225

M3 - Conference contribution

AN - SCOPUS:85133025093

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 119

EP - 127

BT - PODS 2022 - Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

PB - Association for Computing Machinery

T2 - 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022

Y2 - 12 June 2022 through 17 June 2022

ER -