Using Wavelet Packets for Selectivity Estimation
Siniša Ilić, Petar Spalević · The Computer Journal · 2012
The selectivity estimation (estimating the number of records that satisfy query conditions) is an important task for query optimization in modern database management systems (DBMS). For this reason, many DBMS maintain histograms to approximate the frequency distribution of values in the attributes of relations. In this paper, we present wavelet packets as an alternative method to the standard wavelet decomposition for building histograms of the distribution of data stored in relations to the database. This method is tested by approximating the cumulative data distribution of one attribute and the joint distributions of two attributes in a relation using various error measures. Experiments performed on synthetically generated data distributions show that our histograms offer improvements in accuracy over standard wavelet decomposition methods.