Back to papers
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
- 1977
- Venue
- PODS
- Year
- 2025
- Pagerank
- 4.1945683e-05
- Overall Rank
- 10,353 | 27.98%
- DOI
-
10.1145/3725243
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
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 |
| 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,282 |
Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling |
2005 |
VLDB |
9.1073603e-05 |
| 2,752 |
Composable Core-sets for Diversity and Coverage Maximization |
2014 |
PODS |
8.1742326e-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,718 |
Weighted Reservoir Sampling from Distributed Streams |
2019 |
PODS |
5.9749691e-05 |
| 8,901 |
On the Feasibility of Forgetting in Data Streams |
2024 |
PODS |
4.427232e-05 |
| 8,905 |
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms |
2023 |
PODS |
4.427232e-05 |
| 10,901 |
Streaming Algorithms with Few State Changes |
2024 |
PODS |
4.1945683e-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 |
| 4,966 |
Relative Error Streaming Quantiles |
2021 |
PODS |
5.7959749e-05 |
| 10,983 |
A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions |
2024 |
SIGMOD |
4.1945683e-05 |
| 10,901 |
Streaming Algorithms with Few State Changes |
2024 |
PODS |
4.1945683e-05 |
| 3,385 |
Estimating Statistical Aggregates on Probabilistic Data Streams |
2007 |
PODS |
7.1580391e-05 |
| 12,108 |
Space-Efficient Estimation of Statistics over Sub-Sampled Streams |
2012 |
PODS |
4.1945683e-05 |
| 10,981 |
Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality |
2024 |
SIGMOD |
4.1945683e-05 |
| 10,005 |
Finding Heavy-Hitters with Optimal State Changes |
2026 |
PODS |
4.1945683e-05 |
| 5,117 |
Sampling Algorithms in a Stream Operator |
2005 |
SIGMOD |
5.6825418e-05 |
| 1,094 |
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems |
2011 |
PODS |
0.00014129658 |
| 11,320 |
Truly Perfect Samplers for Data Streams and Sliding Windows |
2022 |
PODS |
4.1945683e-05 |