Truly Perfect Samplers for Data Streams and Sliding Windows

Summary: Define “truly perfect” samplers (exact output distribution, ε=γ=0) and prove sublinear-space impossibility in general turnstile streams. Provide a sublinear-space framework for insertion-only and sliding-window streams yielding truly perfect L_p samplers for all p>0 with O(1) updates and extensions to concave and robust measures. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1866
Venue: PODS
Year: 2022
Pagerank: 5.093636e-05
Overall Rank: 11,519 | 20.97%
DOI: 10.1145/3517804.3524139

Incoming Non-self Citations Over Time

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

Authors

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

BibTeX Citation

@inproceedings{jayaram_pods22,
        address = {New York, NY, USA},
        series = {{PODS} '22},
        title = {{Truly Perfect Samplers for Data Streams and Sliding Windows}},
        url = {https://dl.acm.org/doi/10.1145/3517804.3524139},
        doi = {10.1145/3517804.3524139},
        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 = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,646	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.093636e-05
11,123	Streaming Algorithms with Few State Changes	2024	PODS	5.093636e-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.00052982574
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593
2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1271562e-05
2,178	Optimal Sampling From Distributed Streams	2010	PODS	9.0159538e-05
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-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,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
6,696	Matrix Sketching Over Sliding Windows	2016	SIGMOD	5.7985588e-05
7,284	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	5.6560822e-05
7,419	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	5.6229876e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD
2	10,110	Adaptive threshold sampling	2022	SIGMOD
3	11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD
4	5,669	Data Streams with Bounded Deletions	2018	PODS
5	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
6	2,576	Optimal Sampling from Sliding Windows	2009	PODS
7	777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS
8	10,168	Tight Lower Bounds for l2 Sampling	2026	PODS
9	10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS
10	10,646	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS