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.00027063233
Overall Rank: 171 | 98.86%
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.00057610161
26	Models and Issues in Data Stream Systems	2002	PODS	0.00051942573
222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024136952
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
287	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022060616
311	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021315058
316	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021238056
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
374	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019698889
381	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00019497061
457	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00017915659
568	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016221103
690	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014703258
745	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014267268
1,006	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012551491
1,061	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00012207625
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012181459
1,174	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.0001165008
1,511	Self-Tuning, GPU-Accelerated Kernel Density Models for Multidimensional Selectivity Estimation	2015	SIGMOD	0.00010408003
1,583	Deep Learning Models for Selectivity Estimation of Multi-Attribute Queries	2020	SIGMOD	0.00010148362
1,693	Global Optimization of Histograms	2001	SIGMOD	9.8377504e-05
1,740	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7289523e-05
1,754	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7111856e-05
1,896	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4010932e-05
2,154	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9382906e-05
2,305	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6550507e-05
2,438	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	8.4532693e-05
2,563	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.2699925e-05
2,987	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.767043e-05
3,106	Compressing Historical Information in Sensor Networks	2004	SIGMOD	7.6276487e-05
3,168	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	7.5583423e-05
3,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.4165176e-05
3,555	Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning	2021	VLDB	7.1877332e-05
3,653	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.1149642e-05
3,858	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9543709e-05
4,290	One-Pass Wavelet Synopses for Maximum-Error Metrics	2005	VLDB	6.6675308e-05
4,330	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB	6.6454689e-05
4,401	Beyond Simple Aggregates: Indexing for Summary Queries	2011	PODS	6.6051378e-05
4,438	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.5840202e-05
4,480	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.566036e-05
4,956	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	6.326039e-05
4,962	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.3244317e-05
5,031	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS	6.2950911e-05
5,056	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.282339e-05
5,636	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.0385837e-05
5,664	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.0293278e-05
5,800	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9735022e-05
5,837	Pre-training Summarization Models of Structured Datasets for Cardinality Estimation	2022	VLDB	5.9600736e-05
6,040	Hierarchical Subspace Sampling: A Unified Framework for High Dimensional Data Reduction, Selectivity Estimation and Nearest Neighbor Search	2002	SIGMOD	5.8900832e-05
7,266	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.55407e-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	285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
2	277	Optimal Histograms with Quality Guarantees	1998	VLDB
3	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
4	1,080	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD
5	960	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB
6	1,006	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB
7	222	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD
8	3,168	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB
9	311	Approximate Query Processing Using Wavelets	2000	VLDB
10	3,312	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS