Sampling Time-Based Sliding Windows in Bounded Space

Summary: Sampling time-based sliding windows in bounded space; uniform sampling can't guarantee a minimum sample size, so bounded priority sampling (BPS) bounds space and adapts to data rate, with a lower bound on expected size. Stratified sampling via merge-based stratification (MBS) keeps strata roughly equal for even window coverage; feasibility study on large real-world data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4064
Venue: SIGMOD
Year: 2008
Pagerank: 8.1647557e-05
Overall Rank: 2,753 | 81.12%
DOI: 10.1145/1376616.1376657

Incoming Non-self Citations Over Time

Authors

1. Rainer Gemulla (Technical University of Dresden)
2. Wolfgang Lehner (Technical University of Dresden)

BibTeX Citation

@inproceedings{gemulla_sigmod08,
        title = {{Sampling Time-Based Sliding Windows in Bounded Space}},
        author = {Gemulla, Rainer and Lehner, Wolfgang},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376657},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376657},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,178	Optimal Sampling From Distributed Streams	2010	PODS	9.0159538e-05
2,576	Optimal Sampling from Sliding Windows	2009	PODS	8.3964437e-05
2,635	Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges	2021	SIGMOD	8.3200595e-05
5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
6,696	Matrix Sketching Over Sliding Windows	2016	SIGMOD	5.7985588e-05
9,732	External Memory Stream Sampling	2015	PODS	5.2279411e-05
10,110	Adaptive threshold sampling	2022	SIGMOD	5.1347137e-05
10,847	GREAT: Generalized Reservoir Sampling based Triangle Counting Estimation over Streaming Graphs	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.8181027e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
2	3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
3	2,443	Independent Range Sampling	2014	PODS
4	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
5	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS
6	2,178	Optimal Sampling From Distributed Streams	2010	PODS
7	11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS
8	7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS
9	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB
10	2,576	Optimal Sampling from Sliding Windows	2009	PODS