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)

Paper ID: 1806
Venue: PODS
Year: 2020
Pagerank: 6.8299006e-05
Overall Rank: 4,211 | 71.11%
DOI: 10.1145/3375395.3387643

Incoming Non-self Citations Over Time

Authors

1. Omri Ben-Eliezer (Tel Aviv University)
2. Eylon Yogev (Technion)

BibTeX Citation

@inproceedings{beneliezer_pods20,
        address = {New York, NY, USA},
        series = {{PODS} '20},
        title = {{The Adversarial Robustness of Sampling}},
        url = {https://dl.acm.org/doi/10.1145/3375395.3387643},
        doi = {10.1145/3375395.3387643},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ben-Eliezer, Omri and Yogev, Eylon},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.7786745e-05
8,790	Practical Dynamic Extension for Sampling Indexes	2023	SIGMOD	5.3722049e-05
9,060	Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms	2023	PODS	5.3251649e-05
10,645	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	5.093636e-05
10,646	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.093636e-05
11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.093636e-05
11,531	The White-Box Adversarial Data Stream Model	2022	PODS	5.093636e-05

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
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.8254873e-05
3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-05
4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.7786745e-05
5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD	6.3238562e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD
2	11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS
3	5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS
4	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB
5	9,676	Analysis and Application of Adaptive Sampling	2000	PODS
6	8,404	Adaptive Sampling for Geometric Problems over Data Streams	2004	PODS
7	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
8	10,110	Adaptive threshold sampling	2022	SIGMOD
9	11,531	The White-Box Adversarial Data Stream Model	2022	PODS
10	4,291	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS