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.00013024064
Overall Rank: 1,255 | 91.28%
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
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272061
781	Spectral Bloom Filters	2003	SIGMOD	0.00016741046
811	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016425612
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
1,193	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013414989
1,981	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8687545e-05
2,277	Generating Targeted Queries for Database Testing	2008	SIGMOD	9.1241198e-05
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
3,167	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	7.4523397e-05
5,220	Similarity Join Size Estimation using Locality Sensitive Hashing	2011	VLDB	5.6216111e-05
7,827	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	4.6411831e-05
8,350	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5404832e-05
9,082	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	4.3998984e-05
9,838	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	4.2740344e-05
12,370	Stretch 'n' Shrink: Resizing Queries to User Preferences	2008	SIGMOD	4.1945683e-05

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
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
1,105	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00013990395
1,981	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8687545e-05
1,193	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00013414989
372	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354779
11,446	Index-Based Join Size Estimation Using Adaptive Sampling	2021	SIGMOD	4.1945683e-05
1,020	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00014624893
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
811	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016425612
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959