Maintaining Bernoulli Samples over Evolving Multisets

Summary: Maintains Bernoulli samples over arbitrary insertion/deletion streams on multisets (duplicates allowed) without accessing the base multiset, extending Gibbons–Matias counting-sample technique. Tracking counters yield unbiased, lower-variance estimators for frequencies, sums, averages and distinct counts, and enable practical subsampling/merging for memory-limited or distributed settings. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1418
Venue: PODS
Year: 2007
Pagerank: 6.0495154e-05
Overall Rank: 5,891 | 59.59%
DOI: 10.1145/1265530.1265544

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

@inproceedings{gemulla_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Maintaining Bernoulli Samples over Evolving Multisets}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265544},
        doi = {10.1145/1265530.1265544},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gemulla, Rainer and Lehner, Wolfgang and Haas, Peter J.},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,443	Independent Range Sampling	2014	PODS	8.5754434e-05
5,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
7,377	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	5.6297042e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
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
5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	6.1062071e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,335	Reservoir Sampling over Joins	2024	SIGMOD
2	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
3	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
4	802	Random Sampling over Joins Revisited	2018	SIGMOD
5	235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB
6	173	Simple Random Sampling from Relational Databases	1986	VLDB
7	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB
8	2,271	Online Maintenance of Very Large Random Samples	2004	SIGMOD
9	3,803	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD
10	5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB