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.1798806e-05
Overall Rank: 2,633 | 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.00013752994
2,230	Optimal Sampling From Distributed Streams	2010	PODS	8.7889857e-05
2,680	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.1227558e-05
3,090	Persistent Data Sketching	2015	SIGMOD	7.6420011e-05
7,978	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.3978826e-05
10,372	Adaptive threshold sampling	2022	SIGMOD	5.0005386e-05
12,246	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	4.9605343e-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.00051942573
57	On Random Sampling over Joins	1999	SIGMOD	0.0003999751
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
465	Counting Triangles in Data Streams	2006	PODS	0.00017754185
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
1,680	Semantics and Evaluation Techniques for Window Aggregates in Data Streams	2005	SIGMOD	9.8853739e-05
2,184	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.8972748e-05
2,274	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.7041791e-05
2,762	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	8.025285e-05
2,820	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9529694e-05
3,219	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.50928e-05
4,330	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.6454689e-05
4,331	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.644974e-05
4,607	Window-Aware Load Shedding for Aggregation Queries over Data Streams	2006	VLDB	6.4894359e-05
4,708	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4419838e-05
4,895	Estimating arbitrary subset sums with few probes	2005	PODS	6.3498065e-05

Semantically Similar Papers

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