Wavelet-Based Histograms for Selectivity Estimation

Summary: Wavelet-based histograms built via multiresolution decomposition on cumulative distributions for compact selectivity estimation. Online construction and joint distributions yield fast approximate answers, outperforming sampling and prior methods for OLAP queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8747dae89e347507
Venue: SIGMOD
Year: 1998
Pagerank: 0.00027134723
Overall Rank: 169 | 98.87%
DOI: 10.1145/276304.276344

Incoming Non-self Citations Over Time

Authors

1. Yossi Matias (AT&T; Tel Aviv University)
2. Jeffrey Scott Vitter (AT&T; Duke University)
3. Min Wang (Duke University)

BibTeX Citation

@inproceedings{matias_sigmod98,
        title = {{Wavelet-Based Histograms for Selectivity Estimation}},
        author = {Matias, Yossi and Vitter, Jeffrey Scott and Wang, Min},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276344},
        url = {https://dl.acm.org/doi/10.1145/276304.276344},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 64 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024218831
255	The History of Histograms (abridged)	2003	VLDB	0.00022981861
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.0002211981
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021311793
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019829769
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019444411
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017962189
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016245271
692	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014741011
742	Dynamic Multidimensional Histograms	2002	SIGMOD	0.0001431602
1,004	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012594522
1,060	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012224575
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202282
1,173	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011686985
1,508	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010440205
1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010180835
1,687	Global Optimization of Histograms	2001	SIGMOD	9.8655879e-05
1,734	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7545773e-05
1,741	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7382372e-05
1,891	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4184294e-05
2,140	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9682092e-05
2,291	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6872323e-05
2,433	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4766785e-05
2,558	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.3007355e-05
2,974	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7938744e-05
3,092	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.6563998e-05
3,163	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5789852e-05
3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.4424817e-05
3,562	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2046519e-05
3,644	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.1399991e-05
3,851	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9785886e-05
4,272	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.6925708e-05
4,324	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.6656407e-05
4,374	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.6300924e-05
4,416	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.6089486e-05
4,462	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.5880099e-05
4,932	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.3483816e-05
4,933	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	6.3474817e-05
5,004	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.3186165e-05
5,044	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.30014e-05
5,622	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.0614658e-05
5,652	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.0515502e-05
5,785	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9961546e-05
5,840	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	5.9737703e-05
6,032	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.9097667e-05
7,247	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5748328e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
2	275	Optimal Histograms with Quality Guarantees	1998	VLDB
3	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
4	1,077	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD
5	956	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB
6	1,004	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB
7	222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD
8	3,163	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB
9	309	Approximate Query Processing Using Wavelets	2000	VLDB
10	3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS