Database Paper Browser

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
2890
Venue
SIGMOD
Year
1996
Pagerank
0.00020272061
Overall Rank
553 | 96.16%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
18 On Random Sampling over Joins 1999 SIGMOD 0.00092385438
211 Join Synopses for Approximate Query Answering 1999 SIGMOD 0.00033981214
449 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00022846068
475 Mining Database Structure; Or, How to Build a Data Quality Browser 2002 SIGMOD 0.00022303253
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
781 Spectral Bloom Filters 2003 SIGMOD 0.00016741046
1,105 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.00013990395
1,193 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013414989
1,369 Random Sampling over Joins Revisited 2018 SIGMOD 0.00012339777
1,584 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011255801
1,695 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010882793
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1897043e-05
2,368 Online Maintenance of Very Large Random Samples 2004 SIGMOD 8.9501526e-05
2,969 Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models 2017 VLDB 7.7974762e-05
3,593 Graph-Based Synopses for Relational Selectivity Estimation 2006 SIGMOD 6.9385476e-05
3,824 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 6.7260705e-05
4,100 A Bi-Level Bernoulli Scheme for Database Sampling 2004 SIGMOD 6.4531387e-05
4,245 A Disk-Based Join With Probabilistic Guarantees* 2005 SIGMOD 6.3272687e-05
4,435 Sampling Dirty Data for Matching Attributes 2010 SIGMOD 6.1918164e-05
5,220 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 5.6216111e-05
6,548 Query Sampling in DB2 Universal Database 2004 SIGMOD 5.0181595e-05
7,358 Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries 2021 SIGMOD 4.7529363e-05
7,827 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6411831e-05
9,082 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 4.3998984e-05
9,227 Panakos: Chasing the Tails for Multidimensional Data Streams 2023 VLDB 4.3692732e-05
10,039 VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs 2026 SIGMOD 4.1945683e-05
10,149 CorrBound: Cardinality Estimation Accounting for Inter- and Intra-relation Correlations 2026 SIGMOD 4.1945683e-05
10,981 Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality 2024 SIGMOD 4.1945683e-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
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564
59 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064501896
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
134 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00042452811
315 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.0002802103
367 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025509745
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868
811 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016425612
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
5,104 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.6946113e-05
811 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016425612
1,020 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014624893
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
11,446 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD 4.1945683e-05
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
1,193 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013414989
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1897043e-05