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: 9474
Venue: VLDB
Year: 2006
Pagerank: 5.1280225e-05
Overall Rank: 6,286 | 56.28%
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,266	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	9.1540815e-05
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7137441e-05
6,190	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1645517e-05
7,415	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	4.7355557e-05
8,240	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB	4.5522563e-05
12,203	Resiliency-Aware Data Management	2011	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
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
224	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00032746205
726	Load Shedding in a Data Stream Manager	2003	VLDB	0.00017511209
1,974	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.8866171e-05
2,282	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1073603e-05
2,368	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9501526e-05
4,100	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.4531387e-05
4,253	The Power of Sampling in Knowledge Discovery	1994	PODS	6.323083e-05
6,439	(Almost) Hands-Off Information Integration for the Life Sciences	2005	CIDR	5.0612141e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,470	Sampling Big Ideas in Query Optimization	2023	PODS	4.5038423e-05
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
4,694	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	5.9944898e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
6,190	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1645517e-05
2,368	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9501526e-05
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
4,350	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.2645054e-05