A Comparison of Selectivity Estimators for Range Queries on Metric Attributes

Summary: Comparison of nonparametric selectivity estimators for range queries on metric attributes with large domains and limited samples; includes histograms, kernel estimators, and a histogram–kernel hybrid. Kernels perform best on continuously distributed data; the hybrid est. is most promising on real data; key factors: sample size and smoothing (bins). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3103
Venue: SIGMOD
Year: 1999
Pagerank: 5.711623e-05
Overall Rank: 5,082 | 64.65%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
1,737	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00010720294
2,165	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	9.389622e-05
2,629	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.4160309e-05
3,691	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD	6.8383587e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040449103
14	Online Aggregation	1997	SIGMOD	0.0010801504
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
897	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00015528028
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
2,969	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB	7.7974762e-05
2,165	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	9.389622e-05
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837