Perfect Sampling in Turnstile Streams Beyond Small Moments

Summary: Extends perfect G-sampling in turnstile streams to p>2 via sampling-and-rejection; space n^{1-2/p} polylog(n), tight up to polylogs. Delivers a (1+ε)-approximate sample with ε^{-2} n^{1-2/p} polylog(n) space; generalizes to perfect polynomial samplers; applies to log/cap and post-stream subset norm/moment estimation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2009
Venue: PODS
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,646 | 26.96%
DOI: 10.1145/3725243

Incoming Non-self Citations Over Time

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

Authors

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

BibTeX Citation

@inproceedings{woodruff_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{Perfect Sampling in Turnstile Streams Beyond Small Moments}},
        url = {https://dl.acm.org/doi/10.1145/3725243},
        doi = {10.1145/3725243},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Woodruff, David P. and Xie, Shenghao and Zhou, Samson},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,162	On Sketching Trimmed Statistics	2026	PODS	5.093636e-05
10,168	Tight Lower Bounds for l2 Sampling	2026	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
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,959	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS	7.9182968e-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
5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
7,328	On the Feasibility of Forgetting in Data Streams	2024	PODS	5.6435171e-05
9,060	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS	5.3251649e-05
10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS	5.093636e-05
11,123	Streaming Algorithms with Few State Changes	2024	PODS	5.093636e-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	2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
2	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
3	11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD
4	9,537	Finding Heavy-Hitters with Optimal State Changes	2026	PODS
5	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
6	5,669	Data Streams with Bounded Deletions	2018	PODS
7	777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS
8	10,171	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS
9	10,168	Tight Lower Bounds for l2 Sampling	2026	PODS
10	11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS