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: 3097
Venue: SIGMOD
Year: 1998
Pagerank: 0.00027541029
Overall Rank: 168 | 98.85%
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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
257	The History of Histograms (abridged)	2003	VLDB	0.00023154793
280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022454217
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
365	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00020041735
388	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019410042
448	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00018292618
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
697	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014888851
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
977	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012864017
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,071	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012322342
1,156	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00011929041
1,503	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.000105564
1,573	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010328171
1,668	Global Optimization of Histograms	2001	SIGMOD	0.00010057026
1,729	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.908788e-05
1,876	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.5717543e-05
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
2,121	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.1402718e-05
2,269	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.8328424e-05
2,404	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.6225576e-05
2,513	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.48462e-05
3,034	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.8302786e-05
3,070	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7900444e-05
3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.7470414e-05
3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.6057671e-05
3,545	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.3249967e-05
3,575	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.2946291e-05
3,788	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	7.1244416e-05
4,188	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.8448865e-05
4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.8181027e-05
4,285	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.7812351e-05
4,325	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.7605683e-05
4,405	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.7218674e-05
4,819	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.4940349e-05
4,846	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	6.4807645e-05
4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.4600939e-05
4,945	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.4321265e-05
5,490	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.200262e-05
5,522	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.1871697e-05
5,650	Extended Wavelets for Multiple Measures	2003	SIGMOD	6.1337629e-05
5,792	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	6.0871213e-05
5,963	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	6.0267197e-05
7,123	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.6966694e-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	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
2	267	Optimal Histograms with Quality Guarantees	1998	VLDB
3	35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
4	1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD
5	934	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB
6	977	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB
7	213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD
8	3,111	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB
9	307	Approximate Query Processing Using Wavelets	2000	VLDB
10	3,241	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS