DBScholar

Back to papers

Optimal Sampling From Distributed Streams

Summary: Communication-optimal protocols for uniform sampling (with/without replacement) from k distributed streams, handling full-stream and sliding-window (last W items or last w time units) cases. Achieve minimal per-item time and space (optimal or near-optimal up to logs) with matching lower bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1508
Venue
PODS
Year
2010
Pagerank
9.0159538e-05
Overall Rank
2,178 | 85.06%
DOI
10.1145/1807085.1807099

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{cormode_pods10,
        address = {New York, NY, USA},
        series = {{PODS} '10},
        title = {{Optimal Sampling From Distributed Streams}},
        url = {https://dl.acm.org/doi/10.1145/1807085.1807099},
        doi = {10.1145/1807085.1807099},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cormode, Graham and Muthukrishnan, S. and Yi, Ke and Zhang, Qin},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank Citing Paper Year Venue Pagerank
777 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.0001410593
1,146 Graph Sketches: Sparsification, Spanners, and Subgraphs 2012 PODS 0.00011984702
2,635 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 8.3200595e-05
2,638 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.3130624e-05
6,871 Continuous Distributed Counting for Non-monotonic Streams 2012 PODS 5.7496345e-05
11,519 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 5.093636e-05
12,168 Stratified-Sampling over Social Networks Using MapReduce 2014 SIGMOD 5.093636e-05
12,252 Utility-Maximizing Event Stream Suppression 2013 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
550 Distributed Top-K Monitoring 2003 SIGMOD 0.0001663758
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
2,406 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.6187297e-05
2,576 Optimal Sampling from Sliding Windows 2009 PODS 8.3964437e-05
2,596 A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams 2006 SIGMOD 8.3627764e-05
2,753 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 8.1647557e-05
3,832 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS 7.0856664e-05
4,989 Shape Sensitive Geometric Monitoring 2008 PODS 6.4106441e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 11,897 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS
2 8,379 Sampling Big Ideas in Query Optimization 2023 PODS
3 1,045 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB
4 5,068 Weighted Reservoir Sampling from Distributed Streams 2019 PODS
5 550 Distributed Top-K Monitoring 2003 SIGMOD
6 5,193 Sampling Algorithms in a Stream Operator 2005 SIGMOD
7 7,284 Streaming in a Connected World: Querying and Tracking Distributed Data Streams 2007 SIGMOD
8 722 Adaptive Filters for Continuous Queries over Distributed Data Streams 2003 SIGMOD
9 7,713 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB
10 12,054 Scalable Approximate Query Tracking over Highly Distributed Data Streams 2016 SIGMOD