Selectivity Estimation on Synopses Based on Chebyshev Polynomials

Suppose we are given N values of an attribute in a relation. B (BN) numerical values are used to approximate frequency distributions of attribute. To date, two major high-accuracy synopses construction techniques have been proposed in the database literature, namely histograms and Haar wavelets. Still, these approximation techniques have not been previously compared to Chebyshev polynomials. In this paper, we conduct such a comparison the accuracy achieved with synopses based on Chebyshev polynomials to that of other techniques, when estimating frequency distributions. We demonstrate that Chebyshev synopses have three main strong points in comparision to other methods: they achieve higher accuracy as measured by the L1, L2 and L∞ error metrics; they can be built in only O(NB) time complexity; and Chebyshev synopses can be dynamically maintained. Experimental results on synthetic and real-life data clearly demonstrate the effectiveness of our method.