Data Streams with Bounded Deletions

Summary: Introduces α-property streams, interpolating insertion-only and turnstile models by bounding deletion-induced cancellation in Lp norm. For heavy hitters, estimation, and sampling, replaces Θ(log n) space overhead with Θ(log α), with matching or near-matching lower bounds. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: hde2bc71a11b845b6
Venue: PODS
Year: 2018
Pagerank: 5.9977531e-05
Overall Rank: 5,778 | 61.16%
DOI: 10.1145/3196959.3196986

Incoming Non-self Citations Over Time

Authors

1. Rajesh Jayaram (Carnegie Mellon University)
2. David P. Woodruff (Carnegie Mellon University)

BibTeX Citation

@inproceedings{jayaram_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Data Streams with Bounded Deletions}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196986},
        doi = {10.1145/3196959.3196986},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jayaram, Rajesh and Woodruff, David P.},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,381	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.6265793e-05
5,045	KLL± Approximate Quantile Sketches over Dynamic Datasets	2021	VLDB	6.3001279e-05
7,472	On the Feasibility of Forgetting in Data Streams	2024	PODS	5.5168918e-05
7,697	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4754508e-05
11,471	Streaming Algorithms with Few State Changes	2024	PODS	4.9793485e-05
11,538	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.9793485e-05
11,828	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9793485e-05
11,840	The White-Box Adversarial Data Stream Model	2022	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 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.00052121228
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017387321
655	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB	0.00015070228
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013794691
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
4,550	Approximate Frequency Counts over Data Streams	2012	VLDB	6.5402546e-05
4,846	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	6.3824495e-05
5,851	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9718136e-05
6,011	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.9143905e-05
6,395	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7998727e-05
6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7458578e-05
7,557	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	5.4971023e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,350	Range Thresholding on Streams	2016	SIGMOD
2	4,381	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS
3	12,321	Variability in Data Streams	2016	PODS
4	9,719	Finding Heavy-Hitters with Optimal State Changes	2026	PODS
5	1,636	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS
6	11,471	Streaming Algorithms with Few State Changes	2024	PODS
7	10,388	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS
8	11,538	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
9	6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
10	11,945	Frequent Elements with Witnesses in Data Streams	2021	PODS