Database Paper Browser

Back to papers

Optimal Sampling from Sliding Windows

Summary: Optimal deterministic algorithms for sampling (with and without replacement) in sliding-window streams, using O(k) space for fixed windows and O(k log n) for bursty windows. Eliminates over‑sampling/randomized guarantees of prior work and matches tight lower bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1486
Venue
PODS
Year
2009
Pagerank
8.096649e-05
Overall Rank
2,807 | 80.50%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank Citing Paper Year Venue Pagerank
1,117 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.0001386123
2,068 Optimal Sampling From Distributed Streams 2010 PODS 9.638573e-05
3,067 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 7.6247945e-05
3,618 Persistent Data Sketching 2015 SIGMOD 6.9080647e-05
6,758 Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives 2019 PODS 4.9335749e-05
9,961 Adaptive threshold sampling 2022 SIGMOD 4.2254157e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
18 On Random Sampling over Joins 1999 SIGMOD 0.00092569117
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072660894
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036655704
389 Counting Triangles in Data Streams 2006 PODS 0.00024649634
846 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00015949293
2,124 Semantics and Evaluation Techniques for Window Aggregates in Data Streams 2005 SIGMOD 9.4824543e-05
2,269 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1507118e-05
2,403 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.8738166e-05
2,881 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9671512e-05
3,123 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.5270618e-05
3,664 Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams 2003 VLDB 6.8645092e-05
4,177 Density Biased Sampling: An Improved Method for Data Mining and Clustering 2000 SIGMOD 6.3768049e-05
4,347 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.2588401e-05
4,647 Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006 VLDB 6.01732e-05
4,934 Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams 2004 SIGMOD 5.815192e-05
4,961 Estimating arbitrary subset sums with few probes 2005 PODS 5.7992561e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,119 Sampling Algorithms in a Stream Operator 2005 SIGMOD 5.6774637e-05
11,263 Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions 2023 VLDB 4.1905499e-05
12,444 Variance Estimation over Sliding Windows 2007 PODS 4.1905499e-05
9,632 External Memory Stream Sampling 2015 PODS 4.3093476e-05
11,322 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 4.1905499e-05
2,403 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.8738166e-05
846 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00015949293
2,068 Optimal Sampling From Distributed Streams 2010 PODS 9.638573e-05
6,758 Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives 2019 PODS 4.9335749e-05
2,881 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9671512e-05