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: 9666
Venue: VLDB
Year: 2006
Pagerank: 6.8181027e-05
Overall Rank: 4,229 | 70.99%
DOI: 10.14778/1164135.1164200

Incoming Non-self Citations Over Time

Authors

1. Charu C. Aggarwal (International Business Machines T. J. Watson Research Center)

BibTeX Citation

@article{aggarwal_vldb06,
        title = {{On Biased Reservoir Sampling in the Presence of Stream Evolution}},
        author = {Aggarwal, Charu C.},
        journal = {PVLDB},
        series = {{VLDB} '06},
        volume = {29},
        number = {2},
        pages = {607--618},
        doi = {10.14778/1164135.1164200},
        url = {https://doi.org/10.14778/1164135.1164200},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,792	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.7436856e-05
2,576	Optimal Sampling from Sliding Windows	2009	PODS	8.3964437e-05
2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	8.1647557e-05
7,648	Accelerating Aggregation Queries on Unstructured Streams of Data	2023	VLDB	5.575838e-05
9,245	Towards Observability for Production Machine Learning Pipelines	2022	VLDB	5.2992628e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-05
11,700	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	5.093636e-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
9	Online Aggregation	1997	SIGMOD	0.00077458002
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00018373044
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
2,493	Applying the Golden Rule of Sampling for Query Estimation	2001	SIGMOD	8.5070756e-05
2,610	Maintaining Time-Decaying Stream Aggregates	2003	PODS	8.347507e-05
4,188	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.8448865e-05
9,272	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB	5.2945481e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD
2	5,891	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS
3	12,362	Get the Most out of Your Sample: Optimal Unbiased Estimators using Partial Information	2011	PODS
4	235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
5	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
6	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
7	2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD
8	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
9	7,335	Reservoir Sampling over Joins	2024	SIGMOD
10	5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB