Optimal Bounds for Approximate Counting

Jelani Nelson, Huacheng Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

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).

Original languageEnglish (US)
Title of host publicationPODS 2022 - Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherAssociation for Computing Machinery
Pages119-127
Number of pages9
ISBN (Electronic)9781450392600
DOIs
StatePublished - Jun 12 2022
Event41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022 - Philadelphia, United States
Duration: Jun 12 2022Jun 17 2022

Publication series

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

Conference

Conference41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2022
Country/TerritoryUnited States
CityPhiladelphia
Period6/12/226/17/22

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Keywords

  • approximate counting
  • lower bounds
  • streaming

Fingerprint

Dive into the research topics of 'Optimal Bounds for Approximate Counting'. Together they form a unique fingerprint.

Cite this