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: 1913
Venue: PODS
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 10,901 | 24.17%
DOI: 10.1145/3651145

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,005	Finding Heavy-Hitters with Optimal State Changes	2026	PODS	4.1945683e-05
10,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072723062
576	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.00019865648
597	Computing Iceberg Queries Efficiently	1998	VLDB	0.00019475592
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
2,451	Write-limited sorts and joins for persistent memory	2014	VLDB	8.7856313e-05
2,884	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	7.9620506e-05
4,403	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2194225e-05
4,618	Approximate Frequency Counts over Data Streams	2012	VLDB	6.0446717e-05
5,131	Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch	2023	PODS	5.6751843e-05
5,550	Optimal Bounds for Approximate Counting	2022	PODS	5.4422275e-05
9,060	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	4.4039656e-05
11,320	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.1945683e-05
11,332	The White-Box Adversarial Data Stream Model	2022	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
4,403	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2194225e-05
11,823	Variability in Data Streams	2016	PODS	4.1945683e-05
4,133	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	6.4196026e-05
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
6,418	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.0696932e-05
3,102	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5586568e-05
12,108	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1945683e-05
10,005	Finding Heavy-Hitters with Optimal State Changes	2026	PODS	4.1945683e-05