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,399 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2134435e-05 |
| 8,907 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 4.4229886e-05 |
| 9,760 | Practical Dynamic Extension for Sampling Indexes | 2023 | SIGMOD | 4.2838028e-05 |
| 10,363 | On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space | 2025 | PODS | 4.1905499e-05 |
| 10,365 | Perfect Sampling in Turnstile Streams Beyond Small Moments | 2025 | 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 |
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 |
|---|---|---|---|---|
| 126 | Space-Efficient Online Computation of Quantile Summaries | 2001 | SIGMOD | 0.00044753012 |
| 446 | Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets | 1999 | SIGMOD | 0.00023002059 |
| 1,394 | Sketching Streams Through the Net: Distributed Approximate Query Tracking | 2005 | VLDB | 0.00012218557 |
| 2,377 | Online Maintenance of Very Large Random Samples | 2004 | SIGMOD | 8.9359321e-05 |
| 4,080 | Quantiles over Data Streams: An Experimental Study | 2013 | SIGMOD | 6.4619407e-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 |
| 5,119 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD | 5.6774637e-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 | 4.1905499e-05 |
| 2,377 | Online Maintenance of Very Large Random Samples | 2004 | SIGMOD | 8.9359321e-05 |
| 4,716 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 5.9692227e-05 |
| 4,347 | On Biased Reservoir Sampling in the Presence of Stream Evolution | 2006 | VLDB | 6.2588401e-05 |
| 9,524 | Analysis and Application of Adaptive Sampling | 2000 | PODS | 4.3268997e-05 |
| 8,376 | Adaptive Sampling for Geometric Problems over Data Streams | 2004 | PODS | 4.5277777e-05 |
| 5,119 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD | 5.6774637e-05 |
| 9,961 | Adaptive threshold sampling | 2022 | SIGMOD | 4.2254157e-05 |
| 11,334 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 4.1905499e-05 |
| 4,399 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2134435e-05 |