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
h576b597f5f373bb3
Venue
PODS
Year
2010
Pagerank
8.7889857e-05
Overall Rank
2,230 | 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
805 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.00013752994
1,153 Graph Sketches: Sparsification, Spanners, and Subgraphs 2012 PODS 0.00011763855
2,680 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 8.1227558e-05
2,702 Quality and Efficiency in Kernel Density Estimates for Large Data 2013 SIGMOD 8.0958339e-05
7,037 Continuous Distributed Counting for Non-monotonic Streams 2012 PODS 5.5993909e-05
11,878 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 4.9605343e-05
12,508 Stratified-Sampling over Social Networks Using MapReduce 2014 SIGMOD 4.9605343e-05
12,592 Utility-Maximizing Event Stream Suppression 2013 SIGMOD 4.9605343e-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.00036097627
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016238411
1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.0001215545
1,471 Communication-Efficient Distributed Monitoring of Thresholded Counts 2006 SIGMOD 0.00010529345
2,472 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.3988741e-05
2,633 Optimal Sampling from Sliding Windows 2009 PODS 8.1798806e-05
2,658 A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams 2006 SIGMOD 8.1455298e-05
2,820 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9529694e-05
3,932 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS 6.900511e-05
5,140 Shape Sensitive Geometric Monitoring 2008 PODS 6.2436669e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,246 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS
2 8,579 Sampling Big Ideas in Query Optimization 2023 PODS
3 1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB
4 5,222 Weighted Reservoir Sampling from Distributed Streams 2019 PODS
5 565 Distributed Top-K Monitoring 2003 SIGMOD
6 5,341 Sampling Algorithms in a Stream Operator 2005 SIGMOD
7 7,435 Streaming in a Connected World: Querying and Tracking Distributed Data Streams 2007 SIGMOD
8 738 Adaptive Filters for Continuous Queries over Distributed Data Streams 2003 SIGMOD
9 7,889 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB
10 12,398 Scalable Approximate Query Tracking over Highly Distributed Data Streams 2016 SIGMOD