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: 9665
Venue: VLDB
Year: 2006
Pagerank: 6.1062071e-05
Overall Rank: 5,733 | 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,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.6225576e-05
2,872	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	8.0104819e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
5,891	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	6.0495154e-05
7,377	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	5.6297042e-05
8,108	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB	5.4850569e-05
12,398	Resiliency-Aware Data Management	2011	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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
671	Load Shedding in a Data Stream Manager	2003	VLDB	0.00015154516
1,648	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	0.00010120668
2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1271562e-05
2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.8254873e-05
3,803	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	7.1114677e-05
4,584	The Power of Sampling in Knowledge Discovery	1994	PODS	6.6181342e-05
6,532	(Almost) Hands-Off Information Integration for the Life Sciences	2005	CIDR	5.8488924e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,379	Sampling Big Ideas in Query Optimization	2023	PODS
2	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
3	4,800	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD
4	54	On Random Sampling over Joins	1999	SIGMOD
5	5,891	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS
6	2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD
7	235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
8	173	Simple Random Sampling from Relational Databases	1986	VLDB
9	7,335	Reservoir Sampling over Joins	2024	SIGMOD
10	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB