On Biased Reservoir Sampling in the Presence of Stream Evolution

Summary: Biased reservoir sampling using temporal bias to emphasize recent items under evolution, without knowing stream size; memoryless bias enables efficient maintenance. Theoretical results bound the maximum reservoir size, with implications for query estimation and evolution. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9475
Venue: VLDB
Year: 2006
Pagerank: 6.2645054e-05
Overall Rank: 4,350 | 69.74%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Charu C. Aggarwal

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,126	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.4887794e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
2,878	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9706235e-05
7,928	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	4.613455e-05
9,118	Towards Observability for Production Machine Learning Pipelines	2022	VLDB	4.3928288e-05
10,981	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1945683e-05
11,502	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
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
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
2,090	Maintaining Time-Decaying Stream Aggregates	2003	PODS	9.5647927e-05
2,835	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.0448428e-05
4,659	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.0160083e-05
9,068	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB	4.4034035e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,368	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9501526e-05
6,190	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1645517e-05
12,166	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1945683e-05
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
12,108	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1945683e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
5,117	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6825418e-05
2,878	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9706235e-05
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
6,286	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1280225e-05