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.00027126333
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.0005758001
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052097907
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024210103
255	The History of Histograms (abridged)	2003	VLDB	0.00022974524
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022112534
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021376597
312	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.0002130211
371	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019822444
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0001971778
386	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019446558
454	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017955913
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016244162
691	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014737455
743	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014309723
1,004	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012588952
1,058	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012224038
1,065	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012202293
1,173	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.0001168187
1,509	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010436933
1,580	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010177136
1,687	Global Optimization of Histograms	2001	SIGMOD	9.8614576e-05
1,735	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7566604e-05
1,743	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7342409e-05
1,892	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4150583e-05
2,142	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9644817e-05
2,294	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6831732e-05
2,432	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4742372e-05
2,558	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.2968348e-05
2,975	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.7905662e-05
3,094	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.6528924e-05
3,164	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5756378e-05
3,303	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.4400795e-05
3,563	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.2023194e-05
3,646	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.1368554e-05
3,852	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9756022e-05
4,272	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.6896372e-05
4,313	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.667311e-05
4,377	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.6269629e-05
4,418	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.6058591e-05
4,463	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.5861255e-05
4,933	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.3454089e-05
4,936	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	6.3447021e-05
5,007	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.3156906e-05
5,047	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.2972183e-05
5,623	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.0586084e-05
5,653	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.048773e-05
5,787	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9933192e-05
5,835	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	5.9737602e-05
6,034	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.9073944e-05
7,249	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5722715e-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	284	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,078	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD
5	955	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,164	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB
9	309	Approximate Query Processing Using Wavelets	2000	VLDB
10	3,303	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS