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.1249652e-05
Overall Rank
2,789 | 80.60%
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,094 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.00014129658
2,080 Optimal Sampling From Distributed Streams 2010 PODS 9.5899129e-05
3,063 Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges 2021 SIGMOD 7.6321424e-05
3,614 Persistent Data Sketching 2015 SIGMOD 6.9147318e-05
6,755 Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives 2019 PODS 4.9383139e-05
9,962 Adaptive threshold sampling 2022 SIGMOD 4.2294678e-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.00092385438
43 Models and Issues in Data Stream Systems 2002 PODS 0.00072723062
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
392 Counting Triangles in Data Streams 2006 PODS 0.00024556183
848 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.0001597308
2,101 Semantics and Evaluation Techniques for Window Aggregates in Data Streams 2005 SIGMOD 9.5429492e-05
2,282 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1073603e-05
2,404 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.8837279e-05
2,878 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9706235e-05
3,050 Comparing Data Streams Using Hamming Norms (How to Zero In) 2002 VLDB 7.6512619e-05
3,656 Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams 2003 VLDB 6.8714509e-05
4,177 Density Biased Sampling: An Improved Method for Data Mining and Clustering 2000 SIGMOD 6.3835403e-05
4,350 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.2645054e-05
4,649 Window-Aware Load Shedding for Aggregation Queries over Data Streams 2006 VLDB 6.0236001e-05
4,930 Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams 2004 SIGMOD 5.8213082e-05
4,955 Estimating arbitrary subset sums with few probes 2005 PODS 5.8053317e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,117 Sampling Algorithms in a Stream Operator 2005 SIGMOD 5.6825418e-05
11,261 Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions 2023 VLDB 4.1945683e-05
12,435 Variance Estimation over Sliding Windows 2007 PODS 4.1945683e-05
9,632 External Memory Stream Sampling 2015 PODS 4.313481e-05
11,320 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 4.1945683e-05
2,404 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.8837279e-05
848 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.0001597308
2,080 Optimal Sampling From Distributed Streams 2010 PODS 9.5899129e-05
6,755 Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives 2019 PODS 4.9383139e-05
2,878 Sampling Time-Based Sliding Windows in Bounded Space 2008 SIGMOD 7.9706235e-05