The Adversarial Robustness of Sampling
Summary: Shows Bernoulli/reservoir sampling in streaming is vulnerable to fully adaptive adversaries that inspect the current sample—VC-dimension bounds can fail and sublinear samples become unrepresentative. Fix: replace d by log|R|; sample size Ω(log|R|/ε^2) suffices (nearly tight), while exploitable attacks require exponentially large |R|. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Omri Ben-Eliezer
- 2. Eylon Yogev
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,386 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.7943617e-05 |
| 8,932 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 5.4076395e-05 |
| 9,751 | Practical Dynamic Extension for Sampling Indexes | 2023 | SIGMOD | 5.278119e-05 |
| 10,363 | On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space | 2025 | PODS | 5.1725247e-05 |
| 10,365 | Perfect Sampling in Turnstile Streams Beyond Small Moments | 2025 | PODS | 5.1725247e-05 |
| 11,322 | Truly Perfect Samplers for Data Streams and Sliding Windows | 2022 | PODS | 5.1725247e-05 |
| 11,334 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 5.1725247e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 83 | Space-Efficient Online Computation of Quantile Summaries | 2001 | SIGMOD | 0.00036461682 |
| 433 | Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets | 1999 | SIGMOD | 0.00018623769 |
| 1,067 | Sketching Streams Through the Net: Distributed Approximate Query Tracking | 2005 | VLDB | 0.00012431746 |
| 2,267 | Online Maintenance of Very Large Random Samples | 2004 | SIGMOD | 8.9078208e-05 |
| 3,654 | Quantiles over Data Streams: An Experimental Study | 2013 | SIGMOD | 7.2880444e-05 |
| 4,386 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.7943617e-05 |
| 5,018 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 6.4668518e-05 |
| 5,118 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD | 6.4208186e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,841 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD | 5.1725247e-05 |
| 2,267 | Online Maintenance of Very Large Random Samples | 2004 | SIGMOD | 8.9078208e-05 |
| 5,018 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 6.4668518e-05 |
| 4,194 | On Biased Reservoir Sampling in the Presence of Stream Evolution | 2006 | VLDB | 6.9060741e-05 |
| 9,532 | Analysis and Application of Adaptive Sampling | 2000 | PODS | 5.318867e-05 |
| 8,282 | Adaptive Sampling for Geometric Problems over Data Streams | 2004 | PODS | 5.5164702e-05 |
| 5,118 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD | 6.4208186e-05 |
| 9,961 | Adaptive threshold sampling | 2022 | SIGMOD | 5.2142386e-05 |
| 11,334 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 5.1725247e-05 |
| 4,386 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.7943617e-05 |