Streaming Algorithms with Few State Changes

Summary: State-change aware streaming: Omega(n^{1-1/p}) changes for constant-factor F_p moments under read/write asymmetry. (1+eps)-approx algorithms reach the bound with near-optimal space, extend to heavy-hitters, sparse support, entropy estimation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1945
Venue: PODS
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,123 | 23.69%
DOI: 10.1145/3651145

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Rajesh Jayaram (Google)
2. David P. Woodruff (Carnegie Mellon University; Google)
3. Samson Zhou (Texas A&M University)

BibTeX Citation

@inproceedings{jayaram_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{Streaming Algorithms with Few State Changes}},
        url = {https://dl.acm.org/doi/10.1145/3651145},
        doi = {10.1145/3651145},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jayaram, Rajesh and Woodruff, David P. and Zhou, Samson},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,537	Finding Heavy-Hitters with Optimal State Changes	2026	PODS	5.2528121e-05
10,646	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
658	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.0001523554
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593
1,996	Write-limited sorts and joins for persistent memory	2014	VLDB	9.3396464e-05
3,854	Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch	2023	PODS	7.0723123e-05
3,919	Optimal Bounds for Approximate Counting	2022	PODS	7.0176745e-05
4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.7786745e-05
4,460	Approximate Frequency Counts over Data Streams	2012	VLDB	6.689845e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05
9,084	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	5.3251649e-05
11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.093636e-05
11,531	The White-Box Adversarial Data Stream Model	2022	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS
2	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
3	12,026	Variability in Data Streams	2016	PODS
4	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
5	6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
6	3,197	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD
7	5,669	Data Streams with Bounded Deletions	2018	PODS
8	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
9	10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS
10	9,537	Finding Heavy-Hitters with Optimal State Changes	2026	PODS