Weighted Reservoir Sampling from Distributed Streams

Summary: First message-optimal algorithm for weighted sampling without replacement (weighted SWOR) from distributed streams, achieving optimal message, space, and time complexity and a nearly-tight message lower bound (up to log(1/ε)). Uses this primitive to give the first distributed algorithms for residual heavy hitters in skewed-weight streams and to tighten/improve message complexity bounds for distributed L1 (count) tracking, yielding matching lower bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1790
Venue: PODS
Year: 2019
Pagerank: 6.3770298e-05
Overall Rank: 5,068 | 65.23%
DOI: 10.1145/3294052.3319696

Incoming Non-self Citations Over Time

Authors

1. Rajesh Jayaram (Carnegie Mellon University)
2. Gokarna Sharma (Kent State University)
3. Srikanta Tirthapura (Iowa State University)
4. David P. Woodruff (Carnegie Mellon University)

BibTeX Citation

@inproceedings{jayaram_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Weighted Reservoir Sampling from Distributed Streams}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319696},
        doi = {10.1145/3294052.3319696},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jayaram, Rajesh and Sharma, Gokarna and Tirthapura, Srikanta and Woodruff, David P.},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-05
7,142	Efficient Dynamic Weighted Set Sampling and Its Extension	2024	VLDB	5.6917227e-05
9,004	LightRW: FPGA Accelerated Graph Dynamic Random Walks	2023	SIGMOD	5.3343985e-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

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
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,433	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.0001080304
1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010240222
2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	8.1647557e-05
3,856	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	7.0690791e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB
2	12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB
3	12,026	Variability in Data Streams	2016	PODS
4	11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS
5	5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB
6	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
7	5,385	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB
8	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
9	3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
10	2,178	Optimal Sampling From Distributed Streams	2010	PODS