Abstract
Histogram and Wavelet synopses provide useful tools in query optimization and approximate query answering. Traditional wavelet synopsis construction algorithms treat the construction algorithms as the wavelet coefficients selection problem which is called Coefficient Thresholding. However, all these algorithms just focus on the selection of best wavelet coefficients but deal with the unselected ones naively (just setting them to zero). A key problem is whether it can achieve the optimum of error when the unselected ones are set to one single value: zero. In this paper, we consider a novel Wavelet-based Synopsis construction for the known L2 error measure which can handle the unselected wavelet coefficients effectively. We provide a comprehensive theoretical analysis and demonstrate the effectiveness of these algorithms in providing more optimal error significantly through synthetic data sets.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Garofalakis, M.N., Kumar, A.: Wavelet synopses for general error metrics. ACM Trans. Database Syst. 30(4), 888–928 (2005)
Garofalakis, M.N., Gibbons, P.B.: Probabilistic wavelet synopses. ACM Trans. Database Syst. 29, 43–90 (2004)
Garofalakis, M.N., Gibbons, P.B.: Wavelet synopses with error guarantees. In: SIGMOD Conference, pp. 476–487 (2002)
Karras, P., Mamoulis, N.: One-Pass Wavelet Synopses for Maximum-Error Metrics. In: VLDB 2005, pp. 421–432 (2005)
Muthukrishnan, S.: Subquadratic Algorithms for Workload-Aware Haar Wavelet Synopses. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 285–296. Springer, Heidelberg (2005)
Blatter, C.: Wavelets: A Primer. A K Peters (1998)
Li, T., Li, Q., Zhu, S., Ogihara, M.: A survey on wavelet applications in data mining. SIGKDD Explorations Newsletter 4(2), 49–68 (2002)
Matias, Y., Vitter, J.S., Wang, M.: Wavelet-based histograms for selectivity estimation. In: Proc. of SIGMOD Conf., pp. 448–459 (1998)
Chakrabarti, K., Garofalakis, M., Rastogi, R., Shim, K.: Approximate query processing using wavelets. VLDB Journal 10(2-3), 199–223 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sun, C., Lu, Y.S., Zhou, C., Liu, J. (2007). Wavelet Synopsis: Setting Unselected Coefficients to Zero Is Not Optimal. In: Wagner, R., Revell, N., Pernul, G. (eds) Database and Expert Systems Applications. DEXA 2007. Lecture Notes in Computer Science, vol 4653. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74469-6_49
Download citation
DOI: https://doi.org/10.1007/978-3-540-74469-6_49
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74467-2
Online ISBN: 978-3-540-74469-6
eBook Packages: Computer ScienceComputer Science (R0)