Optimal Bounds for Approximate Counting

Summary: Randomized space Θ(log log N + log(1/ε) + log log(1/δ)) bits suffices for (1+ε)-approximate counting w.p. 1−δ, exponentially improving prior log(1/δ) dependence. Also shows Morris Counter (with minor tweak) attains this and proves a matching lower bound (optimal up to ≤3+o(1) factor) with explicit constants. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1894
Venue: PODS
Year: 2022
Pagerank: 7.0176745e-05
Overall Rank: 3,919 | 73.12%
DOI: 10.1145/3517804.3526225

Incoming Non-self Citations Over Time

Authors

1. Jelani Nelson (University of California Berkeley)
2. Huacheng Yu (Princeton University)

BibTeX Citation

@inproceedings{nelson_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{Optimal Bounds for Approximate Counting}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3526225},
        doi = {10.1145/3517804.3526225},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Nelson, Jelani and Yu, Huacheng},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,537	Finding Heavy-Hitters with Optimal State Changes	2026	PODS	5.2528121e-05
10,162	On Sketching Trimmed Statistics	2026	PODS	5.093636e-05
10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS	5.093636e-05
11,093	PolyBase: Adapting to Data Affinity Changes in Geo-Replicated Database via Row-Level Consensus-Group Affiliation Re-Assignment	2025	VLDB	5.093636e-05
11,123	Streaming Algorithms with Few State Changes	2024	PODS	5.093636e-05
11,375	Applications of Sketching and Pathways to Impact	2023	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
451	Mergeable Summaries	2012	PODS	0.00018151445

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,698	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS
2	6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
3	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
4	6,871	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS
5	5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS
6	11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS
7	4,472	Relative Error Streaming Quantiles	2021	PODS
8	4,194	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS
9	1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS
10	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS