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)
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,354 | Hashed Samples: Selectivity Estimators For Set Similarity Selection Queries | 2008 | VLDB | 8.5896515e-05 |
| 2,433 | Cardinality Estimation Using Sample Views with Quality Assurance | 2007 | SIGMOD | 8.4766785e-05 |
| 5,831 | Joins on Samples: A Theoretical Guide for Practitioners | 2020 | VLDB | 5.9782109e-05 |
| 5,851 | A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets | 2006 | VLDB | 5.9718136e-05 |
| 5,985 | A Random Walk Approach to Sampling Hidden Databases | 2007 | SIGMOD | 5.926154e-05 |
| 6,967 | Sampling Dirty Data for Matching Attributes | 2010 | SIGMOD | 5.6323307e-05 |
| 9,764 | Sapprox: Enabling Efficient and Accurate Approximations on Sub-datasets with Distribution-aware Online Sampling | 2017 | VLDB | 5.1344728e-05 |
| 11,079 | Efficient Approximate Query Processing with Block Sampling | 2025 | CIDR | 4.9793485e-05 |
| 11,536 | Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality | 2024 | SIGMOD | 4.9793485e-05 |
Previous
Page 1 / 1
Next
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.00076195956 |
| 57 | On Random Sampling over Joins | 1999 | SIGMOD | 0.00040108301 |
| 58 | Statistical Estimators for Relational Algebra Expressions | 1988 | PODS | 0.00040035279 |
| 138 | Join Synopses for Approximate Query Answering | 1999 | SIGMOD | 0.00029627449 |
| 175 | Simple Random Sampling from Relational Databases | 1986 | VLDB | 0.00026784195 |
| 745 | Bifocal Sampling for Skew-Resistant Join Size Estimation | 1996 | SIGMOD | 0.00014288286 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,831 | Joins on Samples: A Theoretical Guide for Practitioners | 2020 | VLDB |
| 2 | 153 | New Sampling-Based Summary Statistics for Improving Approximate Query Answers | 1998 | SIGMOD |
| 3 | 3,131 | Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates | 2019 | CIDR |
| 4 | 1,678 | Two-Level Sampling for Join Size Estimation | 2017 | SIGMOD |
| 5 | 4,792 | Error-bounded Sampling for Analytics on Big Sparse Data | 2014 | VLDB |
| 6 | 57 | On Random Sampling over Joins | 1999 | SIGMOD |
| 7 | 6,011 | Maintaining Bernoulli Samples over Evolving Multisets | 2007 | PODS |
| 8 | 79 | Practical Selectivity Estimation through Adaptive Sampling | 1990 | SIGMOD |
| 9 | 519 | Random Sampling for Histogram Construction: How much is enough? | 1998 | SIGMOD |
| 10 | 175 | Simple Random Sampling from Relational Databases | 1986 | VLDB |