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: hfa86e17a86d6fe82
Venue: PODS
Year: 2009
Pagerank: 8.2095532e-05
Overall Rank: 2,624 | 82.36%
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
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013794691
2,219	Optimal Sampling From Distributed Streams	2010	PODS	8.8156731e-05
2,669	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.1531412e-05
3,080	Persistent Data Sketching	2015	SIGMOD	7.6662346e-05
7,957	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.4183555e-05
10,338	Adaptive threshold sampling	2022	SIGMOD	5.0195045e-05
12,197	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	4.9793485e-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.00052121228
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
462	Counting Triangles in Data Streams	2006	PODS	0.00017807125
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
1,674	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.922398e-05
2,171	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.9239861e-05
2,260	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.7353589e-05
2,753	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	8.0549317e-05
2,807	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.982663e-05
3,211	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.536045e-05
4,313	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.6699869e-05
4,324	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.6656407e-05
4,590	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.5139479e-05
4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4662079e-05
4,870	Estimating arbitrary subset sums with few probes	2005	PODS	6.3737999e-05

Semantically Similar Papers

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