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

Summary: Introduces Random Pairing, the first reservoir-sampling extension supporting arbitrary insertions and deletions while preserving uniformity and bounded sample size. For growing datasets, proves resizing must access base data and gives a time-minimal resizing algorithm. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hee69c5c1a9fe0666
Venue: VLDB
Year: 2006
Pagerank: 5.9718136e-05
Overall Rank: 5,851 | 60.67%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Rainer Gemulla (Technical University of Dresden)
2. Wolfgang Lehner (Technical University of Dresden)
3. Peter J. Haas (IBM)

BibTeX Citation

@article{gemulla_vldb06,
        title = {{A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets}},
        author = {Gemulla, Rainer and Lehner, Wolfgang and Haas, Peter J.},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {595--606},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,433	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4766785e-05
2,904	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	7.8801067e-05
5,778	Data Streams with Bounded Deletions	2018	PODS	5.9977531e-05
6,011	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.9143905e-05
7,510	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	5.5055437e-05
8,283	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB	5.3627138e-05
12,689	Resiliency-Aware Data Management	2011	VLDB	4.9793485e-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
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027837289
676	Load Shedding in a Data Stream Manager	2003	VLDB	0.00014853749
1,662	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.9465656e-05
2,171	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.9239861e-05
2,322	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.6361485e-05
3,871	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.9543581e-05
4,679	The Power of Sampling in Knowledge Discovery	1994	PODS	6.4726631e-05
6,508	(Almost) Hands-Off Information Integration for the Life Sciences	2005	CIDR	5.760287e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,553	Sampling Big Ideas in Query Optimization	2023	PODS
2	79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
3	4,713	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD
4	57	On Random Sampling over Joins	1999	SIGMOD
5	6,011	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS
6	2,322	Online Maintenance of Very Large Random Samples	2004	SIGMOD
7	242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
8	175	Simple Random Sampling from Relational Databases	1986	VLDB
9	7,467	Reservoir Sampling over Joins	2024	SIGMOD
10	4,324	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB