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: h336df0e25018c435
Venue: SIGMOD
Year: 1999
Pagerank: 6.3474817e-05
Overall Rank: 4,933 | 66.84%
DOI: 10.1145/304182.304203

Incoming Non-self Citations Over Time

Authors

1. Björn Blohsfeld (University of Marburg)
2. Dieter Korus (University of Marburg)
3. Bernhard Seeger (University of Marburg)

BibTeX Citation

@inproceedings{blohsfeld_sigmod99,
        title = {{A Comparison of Selectivity Estimators for Range Queries on Metric Attributes}},
        author = {Blohsfeld, Björn and Korus, Dieter and Seeger, Bernhard},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304203},
        url = {https://dl.acm.org/doi/10.1145/304182.304203},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011777105
1,508	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010440205
2,359	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.5813849e-05
3,281	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD	7.4583561e-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.0023947656
9	Online Aggregation	1997	SIGMOD	0.00076195956
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047863192
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023792809
275	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022413521
519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016942879

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
2	77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB
3	103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB
4	2,162	Selectivity Estimation in Spatial Databases	1999	SIGMOD
5	169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
6	956	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB
7	866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
8	2,216	Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models	2017	VLDB
9	1,508	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD
10	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD