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 14 of 64 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,206	Selectivity Functions of Range Queries are Learnable*	2022	SIGMOD	5.6731116e-05
7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.6625146e-05
7,375	Compact Histograms for Hierarchical Identifiers	2006	VLDB	5.6299286e-05
7,379	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.629255e-05
7,419	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB	5.6229876e-05
9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.3058708e-05
9,642	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD	5.2434488e-05
9,825	Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets	2003	VLDB	5.2143223e-05
10,016	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.1764556e-05
10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.1530576e-05
10,891	Cardinality Estimation for Having-Clauses	2025	VLDB	5.093636e-05
11,957	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB	5.093636e-05
12,532	A Wavelet Transform for Efficient Consolidation of Sensor Relations with Quality Guarantees	2009	VLDB	5.093636e-05
12,578	LEE WAVE: Level-Wise Distribution of Wavelet Coefficients for Processing kNN Queries over Distributed Streams	2008	VLDB	5.093636e-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