{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:29:03Z","timestamp":1765484943597,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T00:00:00Z","timestamp":1133395200000},"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":[[2005,12]]},"abstract":"<jats:p>\n            Several studies have demonstrated the effectiveness of the 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 query answers. Conventional wavelet synopses that greedily minimize the overall root-mean-squared (i.e.,\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            -norm) error in the data approximation can suffer from important problems, including severe bias and wide variance in the quality of the data reconstruction, and lack of nontrivial guarantees for individual approximate answers. Thus,\n            <jats:italic>probabilistic thresholding schemes<\/jats:italic>\n            have been recently proposed as a means of building wavelet synopses that try to\n            <jats:italic>probabilistically<\/jats:italic>\n            control\n            <jats:italic>maximum<\/jats:italic>\n            approximation-error metrics (e.g., maximum relative error).A key open problem is whether it is possible to design efficient\n            <jats:italic>deterministic<\/jats:italic>\n            wavelet-thresholding algorithms for minimizing\n            <jats:italic>\n              general, non-L\n              <jats:sub>2<\/jats:sub>\n              error metrics\n            <\/jats:italic>\n            that are relevant to approximate query processing systems, such as maximum relative or maximum absolute error. Obviously, such algorithms can guarantee better maximum-error wavelet synopses and avoid the pitfalls of probabilistic techniques (e.g., \u201cbad\u201d coin-flip sequences) leading to poor solutions; in addition, they can be used to directly optimize the synopsis construction process for other useful error metrics, such as the\n            <jats:italic>mean relative error<\/jats:italic>\n            in data-value reconstruction. In this article, we propose novel, computationally efficient schemes for deterministic wavelet thresholding with the objective of optimizing\n            <jats:italic>general approximation-error metrics<\/jats:italic>\n            . We first consider the problem of constructing wavelet synopses optimized for\n            <jats:italic>maximum error<\/jats:italic>\n            , and introduce an\n            <jats:italic>optimal<\/jats:italic>\n            low polynomial-time algorithm for\n            <jats:italic>one-dimensional<\/jats:italic>\n            wavelet thresholding---our algorithm is based on a new Dynamic-Programming (DP) formulation, and can be employed to minimize the maximum relative or absolute error in the data reconstruction. Unfortunately, directly extending our one-dimensional DP algorithm to\n            <jats:italic>multidimensional<\/jats:italic>\n            wavelets results in a super-exponential increase in time complexity with the data dimensionality. Thus, we also introduce novel, polynomial-time\n            <jats:italic>approximation schemes<\/jats:italic>\n            (with tunable approximation guarantees) for deterministic wavelet thresholding in multiple dimensions. We then demonstrate how our optimal and approximate thresholding algorithms for maximum error can be extended to handle a broad, natural class of\n            <jats:italic>distributive error metrics<\/jats:italic>\n            , which includes several important error measures, such as mean weighted relative error and weighted\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>\n              <jats:italic>p<\/jats:italic>\n            <\/jats:sub>\n            -norm error. Experimental results on real-world and synthetic data sets evaluate our novel optimization algorithms, and demonstrate their effectiveness against earlier wavelet-thresholding schemes.\n          <\/jats:p>","DOI":"10.1145\/1114244.1114246","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"888-928","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Wavelet synopses for general error metrics"],"prefix":"10.1145","volume":"30","author":[{"given":"Minos","family":"Garofalakis","sequence":"first","affiliation":[{"name":"Intel Research Berkeley, Berkeley, CA"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, New Delhi, India"}]}],"member":"320","published-online":{"date-parts":[[2005,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_2_1","first-page":"3","article-title":"Improving responsiveness for wide-area data access","volume":"20","author":"Amsaleg L.","year":"1997","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007636"},{"volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases","author":"Chakrabarti K.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767147"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872786"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375685"},{"issue":"7","key":"e_1_2_1_8_1","first-page":"51","article-title":"Nonlinear Approximation","author":"DeVore R. A.","year":"1998","journal-title":"Acta"},{"volume-title":"Tutorial in Proceedings of the 27th International Confrence on Very Large Data Bases","author":"Garofalakis M.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564746"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974753"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055582"},{"volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases","author":"Gilbert A. C.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"Guha S. 2004. A note on wavelet optimization. (Manuscript available from: http:\/\/www.cis.upenn.edu\/~sudipto\/note.html.)]]  Guha S. 2004. A note on wavelet optimization. (Manuscript available from: http:\/\/www.cis.upenn.edu\/~sudipto\/note.html.)]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335448"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/130283.130335"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656447"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50011-2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1036095"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276344"},{"volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases","author":"Matias Y.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA.]]   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA.]]","DOI":"10.1017\/CBO9780511814075"},{"volume-title":"Proceedings of the 7th International Conference on Database Theory (ICDT'99)","author":"Muthukrishnan S.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304217"},{"key":"e_1_2_1_27_1","unstructured":"Stollnitz E. J. DeRose T. D. and Salesin D. H. 1996. Wavelets for Computer Graphics---Theory and Applications. Morgan Kaufmann San Francisco CA.]]   Stollnitz E. J. DeRose T. D. and Salesin D. H. 1996. Wavelets for Computer Graphics---Theory and Applications. Morgan Kaufmann San Francisco CA.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304199"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1114244.1114246","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1114244.1114246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:37Z","timestamp":1750262917000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1114244.1114246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1145\/1114244.1114246"],"URL":"https:\/\/doi.org\/10.1145\/1114244.1114246","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2005,12]]},"assertion":[{"value":"2005-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}