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: 1834
Venue: PODS
Year: 2022
Pagerank: 4.1945683e-05
Overall Rank: 11,320 | 21.25%
DOI: 10.1145/3517804.3524139

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,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-05
10,901	Streaming Algorithms with Few State Changes	2024	PODS	4.1945683e-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
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072723062
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
2,080	Optimal Sampling From Distributed Streams	2010	PODS	9.5899129e-05
2,282	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1073603e-05
4,172	The Adversarial Robustness of Sampling	2020	PODS	6.3879072e-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
4,718	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9749691e-05
6,774	Matrix Sketching Over Sliding Windows	2016	SIGMOD	4.9299348e-05
7,334	Streaming in a Connected World: Querying and Tracking Distributed Data Streams	2007	SIGMOD	4.7604215e-05
8,605	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	4.4865144e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,718	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9749691e-05
2,080	Optimal Sampling From Distributed Streams	2010	PODS	9.5899129e-05
12,108	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1945683e-05
2,878	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9706235e-05
9,962	Adaptive threshold sampling	2022	SIGMOD	4.2294678e-05
10,981	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1945683e-05
5,117	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6825418e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
10,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-05