{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T03:21:59Z","timestamp":1792034519872,"version":"4.4.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T00:00:00Z","timestamp":1180656000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:p>\n            Several studies have demonstrated the effectiveness of the Haar wavelet decomposition as a tool for reducing large amounts of data down to compact\n            <jats:italic>wavelet synopses<\/jats:italic>\n            that can be used to obtain fast, accurate approximate answers to user queries. Although originally designed for minimizing the overall mean-squared (i.e.,\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            -norm) error in the data approximation, recently proposed methods also enable the use of Haar wavelets in minimizing other error metrics, such as the relative error in data value reconstruction, which is arguably the most important for approximate query answers. Relatively little attention, however, has been paid to the problem of using wavelet synopses as an approximate query answering tool over complex tabular datasets containing\n            <jats:italic>multiple measures<\/jats:italic>\n            , such as those typically found in real-life OLAP applications. Existing decomposition approaches will either operate on each measure individually, or treat all measures as a vector of values and process them simultaneously. As we demonstrate in this article, these existing\n            <jats:italic>individual<\/jats:italic>\n            or\n            <jats:italic>combined<\/jats:italic>\n            storage approaches for the wavelet coefficients of different measures can easily lead to suboptimal storage utilization, resulting in drastically reduced accuracy for approximate query answers. To address this problem, in this work, we introduce the notion of an\n            <jats:italic>extended<\/jats:italic>\n            wavelet coefficient as a flexible, efficient storage method for wavelet coefficients over multimeasure data. We also propose novel algorithms for constructing effective (optimal or near-optimal) extended wavelet-coefficient synopses under a given storage constraint, for both sum-squared error and relative-error norms. Experimental results with both real-life and synthetic datasets validate our approach, demonstrating that our techniques consistently obtain significant gains in approximation accuracy compared to existing solutions.\n          <\/jats:p>","DOI":"10.1145\/1242524.1242527","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Extended wavelets for multiple measures"],"prefix":"10.1145","volume":"32","author":[{"given":"Antonios","family":"Deligiannakis","sequence":"first","affiliation":[{"name":"University of Athens, Athens, Greece"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"Intel Research, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nick","family":"Roussopoulos","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,6]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767147"},{"key":"e_1_2_2_3_1","unstructured":"Cisco. 1999. Netflow services and applications. White paper. http:\/\/www.cisco.com\/.  Cisco. 1999. Netflow services and applications. White paper. http:\/\/www.cisco.com\/."},{"key":"e_1_2_2_4_1","volume-title":"Sampling Techniques","author":"Cochran W. G.","unstructured":"Cochran , W. G. 1977. Sampling Techniques . John Wiley , New York . Cochran, W. G. 1977. Sampling Techniques. John Wiley, New York."},{"key":"e_1_2_2_5_1","unstructured":"Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. Leiserson C. and Rivest R. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872786"},{"key":"e_1_2_2_7_1","volume-title":"Tech. Rep. CS-TR-4462","author":"Deligiannakis A.","year":"2003","unstructured":"Deligiannakis , A. and Roussopoulos , N . 2003 b. Extended wavelets for multiple measures. Tech. Rep. CS-TR-4462 , University of Maryland. Deligiannakis, A. and Roussopoulos, N. 2003b. Extended wavelets for multiple measures. Tech. Rep. CS-TR-4462, University of Maryland."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/83821"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130291"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases.","author":"Garofalakis M.","unstructured":"Garofalakis , M. and Gibbons , P. B . 2001. Approximate query processing: Taming the terabytes . Proceedings of the 27th International Conference on Very Large Data Bases. Garofalakis, M. and Gibbons, P. B. 2001. Approximate query processing: Taming the terabytes. Proceedings of the 27th International Conference on Very Large Data Bases."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974753"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114246"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases. 79--88","author":"Gilbert A.","unstructured":"Gilbert , A. , Kotidis , Y. , Muthukrishnan , S. , and Strauss , M . 2001. Surfing wavelets on streams: One-Pass summaries for approximate aggregate queries . In Proceedings of the 27th International Conference on Very Large Data Bases. 79--88 . Gilbert, A., Kotidis, Y., Muthukrishnan, S., and Strauss, M. 2001. Surfing wavelets on streams: One-Pass summaries for approximate aggregate queries. In Proceedings of the 27th International Conference on Very Large Data Bases. 79--88."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083642"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases. 288--299","author":"Guha S.","unstructured":"Guha , S. , Kim , C. , and Shim , K . 2004. XWAVE: Approximate extended wavelets for streaming data . In Proceedings of the 30th International Conference on Very Large Data Bases. 288--299 . Guha, S., Kim, C., and Shim, K. 2004. XWAVE: Approximate extended wavelets for streaming data. In Proceedings of the 30th International Conference on Very Large Data Bases. 288--299."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1036095"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases.","author":"Karras P.","unstructured":"Karras , P. and Mamoulis , N . 2005. One-Pass wavelet synopses for maximum-error metrics . In Proceedings of the 31st International Conference on Very Large Data Bases. Karras, P. and Mamoulis, N. 2005. One-Pass wavelet synopses for maximum-error metrics. In Proceedings of the 31st International Conference on Very Large Data Bases."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_25"},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases. 101--110","author":"Matias Y.","unstructured":"Matias , Y. , Vitter , J. , and Wang , M . 2000. Dynamic maintenance of wavelet-based histograms . In Proceedings of the 26th International Conference on Very Large Data Bases. 101--110 . Matias, Y., Vitter, J., and Wang, M. 2000. Dynamic maintenance of wavelet-based histograms. In Proceedings of the 26th International Conference on Very Large Data Bases. 101--110."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276344"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the 8th International Conference on Extending Database Technology (EDBT). 664--681","author":"Schmidt R. R.","unstructured":"Schmidt , R. R. and Shahabi , C . 2002. Propolyne: A fast wavelet-based algorithm for progressive evaluation of polynomial range-sum queries . In Proceedings of the 8th International Conference on Extending Database Technology (EDBT). 664--681 . Schmidt, R. R. and Shahabi, C. 2002. Propolyne: A fast wavelet-based algorithm for progressive evaluation of polynomial range-sum queries. In Proceedings of the 8th International Conference on Extending Database Technology (EDBT). 664--681."},{"key":"e_1_2_2_23_1","unstructured":"Stollnitz E. J. DeRose T. D. and Salesin D. H. 1996. Wavelets for Computer Graphics - Theory and Applications. Morgan Kaufmann San Fransisco CA.   Stollnitz E. J. DeRose T. D. and Salesin D. H. 1996. Wavelets for Computer Graphics - Theory and Applications. Morgan Kaufmann San Fransisco CA."},{"key":"e_1_2_2_24_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer Verlag . Vazirani, V. V. 2001. Approximation Algorithms. Springer Verlag."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304199"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3147.3165"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1242524.1242527","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1242524.1242527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:38:56Z","timestamp":1750268336000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1242524.1242527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["10.1145\/1242524.1242527"],"URL":"https:\/\/doi.org\/10.1145\/1242524.1242527","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6]]},"assertion":[{"value":"2007-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}