DBScholar

Back to papers

Bifocal Sampling for Skew-Resistant Join Size Estimation

Summary: Bifocal sampling classifies tuples into sparse and dense groups and uses estimators tailored to cross-group joinings. With a sample size O(sqrt(n) log n), it achieves high-probability constant-factor accuracy for Omega(n/log n) joins, skew-resistant. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h0d04548e12bedc05
Venue
SIGMOD
Year
1996
Pagerank
0.00014288286
Overall Rank
745 | 95.00%
DOI
10.1145/233269.233340

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ganguly_sigmod96,
        title = {{Bifocal Sampling for Skew-Resistant Join Size Estimation}},
        author = {Ganguly, Sumit and Gibbons, Phillip B. and Matias, Yossi and Silberschatz, Avi},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233340},
        url = {https://dl.acm.org/doi/10.1145/233269.233340},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
57 On Random Sampling over Joins 1999 SIGMOD 0.00040108301
138 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00029627449
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
435 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.0001832766
688 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00014753664
750 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014265196
795 Random Sampling over Joins Revisited 2018 SIGMOD 0.00013938779
870 Spectral Bloom Filters 2003 SIGMOD 0.0001334417
1,319 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011045888
1,678 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.9088372e-05
1,741 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7382372e-05
2,216 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 8.8177753e-05
2,322 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.6361485e-05
3,090 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 7.6584982e-05
3,851 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9785886e-05
3,871 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.9543581e-05
4,217 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.7271293e-05
4,958 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3394776e-05
6,685 Query Sampling in DB2 Universal Database 2004 SIGMOD 5.7086005e-05
6,967 Sampling Dirty Data for Matching Attributes 2010 SIGMOD 5.6323307e-05
7,364 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 5.5418075e-05
8,032 VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs 2026 SIGMOD 5.4035152e-05
8,035 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.4025473e-05
8,325 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3540828e-05
9,509 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 5.1707704e-05
10,627 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 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 10 of 10 cited papers.

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

Rank Cited Paper Year Venue Pagerank
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040035279
77 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00036828234
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036487763
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026389403
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020329113
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017408001
1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012529816
1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011548537
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010734049
1,467 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010567959
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD
2 3,992 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS
3 1,184 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD
4 1,467 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS
5 1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS
6 1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS
7 11,951 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD
8 428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS
9 750 Join Size Estimation Subject to Filter Conditions 2015 VLDB
10 1,678 Two-Level Sampling for Join Size Estimation 2017 SIGMOD