Finding Heavy-Hitters with Optimal State Changes

Summary: Streaming algorithm for ε-ℓ_k heavy-hitters with drastically reduced state-change complexity: O(ε^{-1} n^{1-1/k} · poly(log log n) · log(1/ε)) state changes and O(1/ε^k · polylog n) space for k∈[1,2] (extension to k≥2 incurs n^{1-2/k} extra space). Shows a matching lower bound up to log log n factors and credits the improvement to a new, very simple insertion-only heavy-hitters subroutine. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: 2055
Venue: PODS
Year: 2026
Pagerank: 5.2528121e-05
Overall Rank: 9,537 | 34.57%
DOI: 10.1145/3767714

Incoming Non-self Citations Over Time

Authors

1. William Swartworth (Carnegie Mellon University)
2. David P. Woodruff (Carnegie Mellon University)

BibTeX Citation

@inproceedings{swartworth_pods26,
        address = {New York, NY, USA},
        series = {{PODS} '26},
        title = {{Finding Heavy-Hitters with Optimal State Changes}},
        url = {https://dl.acm.org/doi/10.1145/3767714},
        doi = {10.1145/3767714},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Swartworth, William and Woodruff, David P.},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,158	Improved Lower Bounds for Privacy under Continual Release	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
3,919	Optimal Bounds for Approximate Counting	2022	PODS	7.0176745e-05
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05
11,123	Streaming Algorithms with Few State Changes	2024	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,056	Range Thresholding on Streams	2016	SIGMOD
2	3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
3	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
4	11,520	Approximately Counting Subgraphs in Data Streams	2022	PODS
5	1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS
6	3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS
7	6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS
8	5,669	Data Streams with Bounded Deletions	2018	PODS
9	6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
10	11,123	Streaming Algorithms with Few State Changes	2024	PODS