{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T05:21:01Z","timestamp":1672291261006},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:p>\n            Several wavelet synopsis construction algorithms were previously proposed based on dynamic programming for unrestricted Haar wavelet synopses as well as Haar\n            <jats:sup>+<\/jats:sup>\n            synopses. However, they find an optimal synopsis for every incoming value in each node of a coefficient tree, even if different incoming values share an identical optimal synopsis. To alleviate the limitation, we present novel algorithms, which keep only a minimal set of the distinct optimal synopses in each node of the tree, for the error-bounded synopsis problem. Furthermore, we propose the methods to restrict coefficient values to be considered to compute the optimal synopses in each node. In addition, by partitioning all optimal synopses in each node into a set of groups, such that every group can be represented by a compact representation, we significantly improve the performance of the proposed algorithms.\n          <\/jats:p>","DOI":"10.14778\/3151113.3151117","type":"journal-article","created":{"date-parts":[[2017,10,19]],"date-time":"2017-10-19T12:30:08Z","timestamp":1508416208000},"page":"40-52","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Haar\n            <sup>+<\/sup>\n            synopsis construction for the maximum absolute error measure"],"prefix":"10.14778","volume":"11","author":[{"given":"Jinhyun","family":"Kim","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun-Ki","family":"Min","sequence":"additional","affiliation":[{"name":"Korea Univ. of Technology and Education, Cheonan, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyuseok","family":"Shim","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.844498"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568520"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974753"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055582"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114246"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198389"},{"key":"e_1_2_1_8_1","first-page":"409","volume-title":"VLDB","author":"Guha S.","year":"2005","unstructured":"S. Guha . Space efficiency in synopsis construction algorithms . In VLDB , pages 409 -- 420 , 2005 . S. Guha. Space efficiency in synopsis construction algorithms. In VLDB, pages 409--420, 2005."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0083-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081884"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.913569"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0052-3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078324.2078327"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687703"},{"key":"e_1_2_1_15_1","first-page":"421","volume-title":"VLDB","author":"Karras P.","year":"2005","unstructured":"P. Karras and N. Mamoulis . One-pass wavelet synopses for maximum-error metrics . In VLDB , pages 421 -- 432 , 2005 . P. Karras and N. Mamoulis. One-pass wavelet synopses for maximum-error metrics. In VLDB, pages 421--432, 2005."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367889"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386124"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281235"},{"key":"e_1_2_1_19_1","volume-title":"Efficient Haar+ synopsis construction for the maximum absolute error measure. Technical report","author":"Kim J.","year":"2017","unstructured":"J. Kim , J. Min , and K. Shim . Efficient Haar+ synopsis construction for the maximum absolute error measure. Technical report , Seoul National University , 2017 . http:\/\/kdd.snu.ac.kr\/~shim\/TR\/TRHaarP.pdf. J. Kim, J. Min, and K. Shim. Efficient Haar+ synopsis construction for the maximum absolute error measure. Technical report, Seoul National University, 2017. http:\/\/kdd.snu.ac.kr\/~shim\/TR\/TRHaarP.pdf."},{"key":"e_1_2_1_20_1","volume-title":"Academic press","author":"Mallat S.","year":"1999","unstructured":"S. Mallat . A wavelet tour of signal processing. Academic press , 1999 . S. Mallat. A wavelet tour of signal processing. Academic press, 1999."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276344"},{"key":"e_1_2_1_22_1","first-page":"101","volume-title":"VLDB","author":"Matias Y.","year":"2000","unstructured":"Y. Matias , J. S. Vitter , and M. Wang . Dynamic maintenance of wavelet-based histograms . In VLDB , pages 101 -- 110 , 2000 . Y. Matias, J. S. Vitter, and M. Wang. Dynamic maintenance of wavelet-based histograms. In VLDB, pages 101--110, 2000."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_23"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304217"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9571-9"},{"key":"e_1_2_1_26_1","first-page":"870","volume-title":"VLDB","author":"Reiss F.","year":"2006","unstructured":"F. Reiss , M. Garofalakis , and J. M. Hellerstein . Compact histograms for hierarchical identifiers . In VLDB , pages 870 -- 881 , 2006 . F. Reiss, M. Garofalakis, and J. M. Hellerstein. Compact histograms for hierarchical identifiers. In VLDB, pages 870--881, 2006."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304199"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3151113.3151117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:33:32Z","timestamp":1672223612000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3151113.3151117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.14778\/3151113.3151117"],"URL":"https:\/\/doi.org\/10.14778\/3151113.3151117","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,9]]}}}