{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T12:51:11Z","timestamp":1673355071302},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            The Lattice Histogram is a recently proposed data summarization technique that achieves approximation quality preferable to that of an optimal plain histogram. Like other hierarchical synopsis methods, a lattice histogram (LH) aims to approximate data using a hierarchical structure. Still, this structure is not defined a priori; it consists an\n            <jats:italic>unknown<\/jats:italic>\n            , not a given, of the problem. Past work has defined the properties that an LH needs to obey and developed general-purpose approximation algorithms for the construction thereof. Still, two major issues remain unaddressed: First, the construction of an\n            <jats:italic>optimal<\/jats:italic>\n            LH for a given error metric is a problem unsolved to date. Second, the proposed algorithms suffer from too high space and time complexities that render their application in real-world settings problematic. In this paper, we address both these questions, focusing on the case that the target error metric is a\n            <jats:italic>maximum<\/jats:italic>\n            error metric. Our algorithms treat both the error-bounded LH construction problem, in which the space occupied by an LH is minimized under an error constraint, as well as the classic space-bounded problem. First, we develop a dynamic-programming scheme that detects an optimal LH under a given maximum-error bound. Second, we propose an efficient, practical, greedy algorithm that solves the same problem with much lower time and space requirements. Then, we show how both our algorithms can be applied to the classic space-bounded problem, aiming at minimizing error under a bound on space. Our experimental study with real-world data sets shows the effectiveness of our methods compared to competing summarization techniques. Moreover, our findings show that our greedy heuristic performs almost as well as the optimal solution in terms of accuracy.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687703","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"670-681","source":"Crossref","is-referenced-by-count":4,"title":["Optimality and scalability in lattice histogram construction"],"prefix":"10.14778","volume":"2","author":[{"given":"Panagiotis","family":"Karras","sequence":"first","affiliation":[{"name":"National University of Singapore"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304198"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375686"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0050-5"},{"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\/568518.568520"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066677.1066817"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/974750.974753"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114246"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/314500.315083"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/581751.581753"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0083-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.913569"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132863.1132873"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1039"},{"key":"e_1_2_1_16_1","volume-title":"VLDB","author":"Guha S.","year":"2004","unstructured":"S. Guha , K. Shim , and J. Woo . REHIST: Relative error histogram construction algorithms . In VLDB , 2004 . S. Guha, K. Shim, and J. Woo. REHIST: Relative error histogram construction algorithms. In VLDB, 2004."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0090-4"},{"key":"e_1_2_1_18_1","volume-title":"VLDB","author":"Ioannidis Y. E.","year":"1993","unstructured":"Y. E. Ioannidis . Universality of serial histograms . In VLDB , 1993 . Y. E. Ioannidis. Universality of serial histograms. In VLDB, 1993."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645505.656447"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315455"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223841"},{"key":"e_1_2_1_22_1","volume-title":"VLDB","author":"Ioannidis Y. E.","year":"1999","unstructured":"Y. E. Ioannidis and V. Poosala . Histogram-based approximation of set-valued query-answers . In VLDB , 1999 . Y. E. Ioannidis and V. Poosala. Histogram-based approximation of set-valued query-answers. In VLDB, 1999."},{"key":"e_1_2_1_23_1","volume-title":"VLDB","author":"Jagadish H. V.","year":"1998","unstructured":"H. V. Jagadish , N. Koudas , S. Muthukrishnan , V. Poosala , K. C. Sevcik , and T. Suel . Optimal histograms with quality guarantees . In VLDB , 1998 . H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In VLDB, 1998."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516447"},{"key":"e_1_2_1_25_1","volume-title":"VLDB","author":"Karras P.","year":"2005","unstructured":"P. Karras and N. Mamoulis . One-pass wavelet synopses for maximum-error metrics . In VLDB , 2005 . P. Karras and N. Mamoulis. One-pass wavelet synopses for maximum-error metrics. In VLDB, 2005."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367889"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386124"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497433"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281235"},{"key":"e_1_2_1_30_1","volume-title":"VLDB","author":"K\u00f6nig A. C.","year":"1999","unstructured":"A. C. K\u00f6nig and G. Weikum . Combining histograms and parametric curve fitting for feedback-driven query result-size estimation . In VLDB , 1999 . A. C. K\u00f6nig and G. Weikum. Combining histograms and parametric curve fitting for feedback-driven query result-size estimation. In VLDB, 1999."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/772862.772870"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276344"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9892.1994.tb00186.x"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50205"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_23"},{"issue":"4","key":"e_1_2_1_36_1","first-page":"5","article-title":"Approximate query answering using histograms","volume":"22","author":"Poosala V.","year":"1999","unstructured":"V. Poosala , V. Ganti , and Y. E. Ioannidis . Approximate query answering using histograms . IEEE Data Eng. Bull. , 22 ( 4 ): 5 -- 14 , 1999 . V. Poosala, V. Ganti, and Y. E. Ioannidis. Approximate query answering using histograms. IEEE Data Eng. Bull., 22(4):5--14, 1999.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_37_1","volume-title":"VLDB","author":"Poosala V.","year":"1997","unstructured":"V. Poosala and Y. E. Ioannidis . Selectivity estimation without the attribute value independence assumption . In VLDB , 1997 . V. Poosala and Y. E. Ioannidis. Selectivity estimation without the attribute value independence assumption. In VLDB, 1997."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233342"},{"key":"e_1_2_1_39_1","volume-title":"VLDB","author":"Reiss F.","year":"2006","unstructured":"F. Reiss , M. Garofalakis , and J. M. Hellerstein . Compact histograms for hierarchical identifiers . In VLDB , 2006 . F. Reiss, M. Garofalakis, and J. M. Hellerstein. Compact histograms for hierarchical identifiers. In VLDB, 2006."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972764.28"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304199"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0015-0"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:30:47Z","timestamp":1672227047000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687703"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687703"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687703","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}