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,403 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2194225e-05 |
| 8,905 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS | 4.427232e-05 |
| 9,758 | Practical Dynamic Extension for Sampling Indexes | 2023 | SIGMOD | 4.2879116e-05 |
| 10,351 | On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space | 2025 | PODS | 4.1945683e-05 |
| 10,353 | Perfect Sampling in Turnstile Streams Beyond Small Moments | 2025 | 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 |
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.00044744986 |
| 443 | Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets | 1999 | SIGMOD | 0.00022996573 |
| 1,392 | Sketching Streams Through the Net: Distributed Approximate Query Tracking | 2005 | VLDB | 0.00012229045 |
| 2,368 | Online Maintenance of Very Large Random Samples | 2004 | SIGMOD | 8.9501526e-05 |
| 4,076 | Quantiles over Data Streams: An Experimental Study | 2013 | SIGMOD | 6.4680854e-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 |
| 5,117 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD | 5.6825418e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,833 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD | 4.1945683e-05 |
| 2,368 | Online Maintenance of Very Large Random Samples | 2004 | SIGMOD | 8.9501526e-05 |
| 4,718 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 5.9749691e-05 |
| 4,350 | On Biased Reservoir Sampling in the Presence of Stream Evolution | 2006 | VLDB | 6.2645054e-05 |
| 9,523 | Analysis and Application of Adaptive Sampling | 2000 | PODS | 4.331052e-05 |
| 8,377 | Adaptive Sampling for Geometric Problems over Data Streams | 2004 | PODS | 4.5321044e-05 |
| 5,117 | Sampling Algorithms in a Stream Operator | 2005 | SIGMOD | 5.6825418e-05 |
| 9,962 | Adaptive threshold sampling | 2022 | SIGMOD | 4.2294678e-05 |
| 11,332 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 4.1945683e-05 |
| 4,403 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2194225e-05 |