A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets

Summary: Proposes Random Pairing (RP): bounded-size sample maintenance for evolving data; extends reservoir sampling to deletions. Stable data: RP yields fast samples; growing data: minimal-time resize touches base; experiments confirm speed and stability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9475
Venue: VLDB
Year: 2006
Pagerank: 5.1231886e-05
Overall Rank: 6,285 | 56.32%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,271	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	9.1467959e-05
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7082045e-05
6,192	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1596405e-05
7,414	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	4.7312542e-05
8,235	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB	4.5481384e-05
12,211	Resiliency-Aware Data Management	2011	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
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032743209
723	Load Shedding in a Data Stream Manager	2003	VLDB	0.00017493042
1,976	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.8784644e-05
2,269	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1507118e-05
2,377	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9359321e-05
4,100	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.4473679e-05
4,250	The Power of Sampling in Knowledge Discovery	1994	PODS	6.3162039e-05
6,433	(Almost) Hands-Off Information Integration for the Life Sciences	2005	CIDR	5.0563606e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,467	Sampling Big Ideas in Query Optimization	2023	PODS	4.4995247e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
4,689	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	5.9899401e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
6,192	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1596405e-05
2,377	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9359321e-05
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
8,964	Reservoir Sampling over Joins	2024	SIGMOD	4.4163852e-05
4,347	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2588401e-05