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: 1485
Venue: PODS
Year: 2009
Pagerank: 8.3964437e-05
Overall Rank: 2,576 | 82.33%
DOI: 10.1145/1559795.1559818

Incoming Non-self Citations Over Time

Authors

1. Vladimir Braverman (University of California Los Angeles)
2. Rafail Ostrovsky (University of California Los Angeles)
3. Carlo Zaniolo (University of California Los Angeles)

BibTeX Citation

@inproceedings{braverman_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Optimal Sampling from Sliding Windows}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559818},
        doi = {10.1145/1559795.1559818},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Braverman, Vladimir and Ostrovsky, Rafail and Zaniolo, Carlo},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 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
2,178	Optimal Sampling From Distributed Streams	2010	PODS	9.0159538e-05
2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.3200595e-05
3,023	Persistent Data Sketching	2015	SIGMOD	7.8398269e-05
7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.5422948e-05
10,110	Adaptive threshold sampling	2022	SIGMOD	5.1347137e-05
11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	5.093636e-05

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
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
1,703	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.9673138e-05
2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1271562e-05
2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.9331834e-05
2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	8.1647557e-05
3,150	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.7055991e-05
3,255	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	7.591663e-05
4,222	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.8227421e-05
4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.8181027e-05
4,517	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.6481605e-05
4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.6133976e-05
4,761	Estimating arbitrary subset sums with few probes	2005	PODS	6.5196044e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,460	Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions	2023	VLDB
2	12,629	Variance Estimation over Sliding Windows	2007	PODS
3	11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS
4	9,732	External Memory Stream Sampling	2015	PODS
5	11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS
6	2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS
7	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS
8	2,178	Optimal Sampling From Distributed Streams	2010	PODS
9	7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS
10	2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD