Database Paper Browser

Back to papers

Fixed-Precision Estimation of Join Selectivity

Summary: Establishes a partial ordering of variability among sampling-based equijoin-selectivity estimators for any fixed sample budget. Presents a general method to convert fixed-step estimators into asymptotically efficient fixed-precision procedures, derives cost orderings, and gives a top index-free algorithm. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
999
Venue
PODS
Year
1993
Pagerank
0.00013018797
Overall Rank
1,254 | 91.29%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272747
778 Spectral Bloom Filters 2003 SIGMOD 0.00016729191
803 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016438972
849 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015919478
1,194 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013411666
1,978 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 9.8764627e-05
2,280 Generating Targeted Queries for Database Testing 2008 SIGMOD 9.1247368e-05
2,369 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 8.9462051e-05
3,133 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 7.4979168e-05
5,222 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 5.6180462e-05
7,833 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 4.6367487e-05
8,345 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 4.5361313e-05
9,079 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 4.3956812e-05
9,837 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 4.269939e-05
12,378 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank Cited Paper Year Venue Pagerank
37 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00075597514
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888
133 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00043220055
291 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00028778973
369 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025502381
751 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017155121
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
18 On Random Sampling over Joins 1999 SIGMOD 0.00092569117
1,104 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR 0.0001398479
1,978 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 9.8764627e-05
1,194 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00013411666
373 Selectivity Estimation using Probabilistic Models 2001 SIGMOD 0.00025354685
11,449 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD 4.1905499e-05
1,019 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00014623543
2,254 Two-Level Sampling for Join Size Estimation 2017 SIGMOD 9.1871115e-05
803 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016438972
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888