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: heb36867d1c50ca24
Venue: PODS
Year: 2007
Pagerank: 5.9143905e-05
Overall Rank: 6,011 | 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,495	Independent Range Sampling	2014	PODS	8.3873598e-05
5,778	Data Streams with Bounded Deletions	2018	PODS	5.9977531e-05
7,510	Efficient and Scalable Statistics Gathering for Large Databases in Oracle 11g	2008	SIGMOD	5.5055437e-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
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026784195
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
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
5,851	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9718136e-05

Semantically Similar Papers

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