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.1905499e-05
- Overall Rank
- 10,365 | 27.97%
- 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.00051431888 |
| 184 |
New Sampling-Based Summary Statistics for Improving Approximate Query Answers |
1998 |
SIGMOD |
0.00036655704 |
| 369 |
Sequential Sampling Procedures For Query Size Estimation |
1992 |
SIGMOD |
0.00025502381 |
| 1,117 |
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems |
2011 |
PODS |
0.0001386123 |
| 2,269 |
Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling |
2005 |
VLDB |
9.1507118e-05 |
| 2,756 |
Composable Core-sets for Diversity and Coverage Maximization |
2014 |
PODS |
8.1682323e-05 |
| 4,170 |
The Adversarial Robustness of Sampling |
2020 |
PODS |
6.381766e-05 |
| 4,399 |
A Framework for Adversarially Robust Streaming Algorithms |
2020 |
PODS |
6.2134435e-05 |
| 4,716 |
Weighted Reservoir Sampling from Distributed Streams |
2019 |
PODS |
5.9692227e-05 |
| 8,902 |
On the Feasibility of Forgetting in Data Streams |
2024 |
PODS |
4.4229886e-05 |
| 8,907 |
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms |
2023 |
PODS |
4.4229886e-05 |
| 10,905 |
Streaming Algorithms with Few State Changes |
2024 |
PODS |
4.1905499e-05 |
| 11,322 |
Truly Perfect Samplers for Data Streams and Sliding Windows |
2022 |
PODS |
4.1905499e-05 |
| 11,334 |
The White-Box Adversarial Data Stream Model |
2022 |
PODS |
4.1905499e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 4,969 |
Relative Error Streaming Quantiles |
2021 |
PODS |
5.790405e-05 |
| 10,986 |
A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions |
2024 |
SIGMOD |
4.1905499e-05 |
| 10,905 |
Streaming Algorithms with Few State Changes |
2024 |
PODS |
4.1905499e-05 |
| 3,391 |
Estimating Statistical Aggregates on Probabilistic Data Streams |
2007 |
PODS |
7.1427968e-05 |
| 12,116 |
Space-Efficient Estimation of Statistics over Sub-Sampled Streams |
2012 |
PODS |
4.1905499e-05 |
| 10,984 |
Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality |
2024 |
SIGMOD |
4.1905499e-05 |
| 10,004 |
Finding Heavy-Hitters with Optimal State Changes |
2026 |
PODS |
4.1905499e-05 |
| 5,119 |
Sampling Algorithms in a Stream Operator |
2005 |
SIGMOD |
5.6774637e-05 |
| 1,117 |
Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems |
2011 |
PODS |
0.0001386123 |
| 11,322 |
Truly Perfect Samplers for Data Streams and Sliding Windows |
2022 |
PODS |
4.1905499e-05 |