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: 9476
Venue: VLDB
Year: 2006
Pagerank: 6.2588401e-05
Overall Rank: 4,347 | 69.79%
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,129	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.4799835e-05
2,807	Optimal Sampling from Sliding Windows	2009	PODS	8.096649e-05
2,881	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9671512e-05
7,911	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	4.6143141e-05
9,116	Towards Observability for Production Machine Learning Pipelines	2022	VLDB	4.3886184e-05
10,984	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1905499e-05
11,506	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.1905499e-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.0010813443
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
446	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00023002059
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
2,094	Maintaining Time-Decaying Stream Aggregates	2003	PODS	9.5556069e-05
2,840	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.0417349e-05
4,656	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.0101164e-05
9,067	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB	4.3991821e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,377	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9359321e-05
6,192	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1596405e-05
12,174	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS	4.1905499e-05
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
12,116	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1905499e-05
2,952	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8230109e-05
2,881	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.9671512e-05
5,119	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6774637e-05
8,964	Reservoir Sampling over Joins	2024	SIGMOD	4.4163852e-05
6,285	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1231886e-05