A Bi-Level Bernoulli Scheme for Database Sampling

Summary: Bi-level Bernoulli sampling unites row- and page-level sampling for ISO-style queries, enabling a tunable speed–precision trade-off with SQL extensions and data-aware parameter optimization. A bang-bang policy governed by a page-heterogeneity index (PHI) guides parameter choice; pilot sampling or catalog statistics set PHI, with a heuristic achieving near-optimal accuracy on clustered or skewed data across 1,100 experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3587
Venue: SIGMOD
Year: 2004
Pagerank: 7.1114677e-05
Overall Rank: 3,803 | 73.91%
DOI: 10.1145/1007568.1007601

Incoming Non-self Citations Over Time

Authors

1. Peter J. Haas (IBM)
2. Christian König (Berufsakademie Stuttgart; IBM)

BibTeX Citation

@inproceedings{haas_sigmod04,
        title = {{A Bi-Level Bernoulli Scheme for Database Sampling}},
        author = {Haas, Peter J. and König, Christian},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007601},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007601},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,308	Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries	2008	VLDB	8.7738996e-05
2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.6225576e-05
5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	6.1062071e-05
5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	6.1025457e-05
5,868	A Random Walk Approach to Sampling Hidden Databases	2007	SIGMOD	6.0613238e-05
6,827	Sampling Dirty Data for Matching Attributes	2010	SIGMOD	5.7616041e-05
9,591	Sapprox: Enabling Efficient and Accurate Approximations on Sub-datasets with Distribution-aware Online Sampling	2017	VLDB	5.2518295e-05
10,634	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-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
9	Online Aggregation	1997	SIGMOD	0.00077458002
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
2	149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
3	3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
4	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
5	54	On Random Sampling over Joins	1999	SIGMOD
6	4,696	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB
7	5,891	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS
8	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
9	508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD
10	173	Simple Random Sampling from Relational Databases	1986	VLDB