{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:21Z","timestamp":1759637781345,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,3,1]],"date-time":"2005-03-01T00:00:00Z","timestamp":1109635200000},"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,3]]},"abstract":"<jats:p>\n            We study the problem of economical representation of subsets of structured sets, which are sets equipped with a set cover or a family of preorders. Given a structured set\n            <jats:italic>U<\/jats:italic>\n            , and a language L whose expressions define subsets of\n            <jats:italic>U<\/jats:italic>\n            , the problem of minimum description length in L (L-MDL) is: \u201cgiven a subset\n            <jats:italic>V<\/jats:italic>\n            of\n            <jats:italic>U<\/jats:italic>\n            , find a shortest string in L that defines\n            <jats:italic>V<\/jats:italic>\n            .\u201d Depending on the structure and the language, the MDL-problem is in general intractable. We study the complexity of the MDL-problem for various structures and show that certain specializations are tractable. The families of focus are hierarchy, linear order, and their multidimensional extensions; these are found in the context of statistical and OLAP databases. In the case of general OLAP databases, data organization is a mixture of multidimensionality, hierarchy, and ordering, which can also be viewed naturally as a cover-structured ordered set. Efficient algorithms are provided for the MDL-problem for hierarchical and linearly ordered structures, and we prove that the multidimensional extensions are NP-complete. Finally, we illustrate the application of the theory to summarization of large result sets and (multi) query optimization for ROLAP queries.\n          <\/jats:p>","DOI":"10.1145\/1061318.1061324","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"211-248","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Concise descriptions of subsets of structured sets"],"prefix":"10.1145","volume":"30","author":[{"given":"Ken Q.","family":"Pu","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}]},{"given":"Alberto O.","family":"Mendelzon","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}]}],"member":"320","published-online":{"date-parts":[[2005,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276314"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of ICDE","author":"Agrawal R.","year":"1997","unstructured":"Agrawal , R. , Gupta , A. , and Sarawagi , S . 1997. Modeling multidimensional databases . In Proceedings of ICDE 1997 . 232--243.]] Agrawal, R., Gupta, A., and Sarawagi, S. 1997. Modeling multidimensional databases. In Proceedings of ICDE 1997. 232--243.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1080\/01969728008927632"},{"volume-title":"Proceedings of the 6th DBPL Workshop. 319--335","author":"Cabibbo L.","key":"e_1_2_1_4_1","unstructured":"Cabibbo , L. and Torlone , R . 1997. Querying multidimensional databases . In Proceedings of the 6th DBPL Workshop. 319--335 .]] Cabibbo, L. and Torlone, R. 1997. Querying multidimensional databases. In Proceedings of the 6th DBPL Workshop. 319--335.]]"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of EDBT","author":"Cabibbo L.","year":"1998","unstructured":"Cabibbo , L. and Torlone , R . 1998. A logical approach to multidimensional databases . In Proceedings of EDBT 1998 . 183--197.]] Cabibbo, L. and Torlone, R. 1998. A logical approach to multidimensional databases. In Proceedings of EDBT 1998. 183--197.]]"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of ICDT","author":"Edmonds J.","year":"2001","unstructured":"Edmonds , J. , Gryz , J. , Liang , D. , and Miller , R. J . 2001. Mining for empty rectangles in large data sets . In Proceedings of ICDT 2001 . 174--188.]] Edmonds, J., Gryz, J., Liang, D., and Miller, R. J. 2001. Mining for empty rectangles in large data sets. In Proceedings of ICDT 2001. 174--188.]]"},{"key":"e_1_2_1_7_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York NY.]]   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York NY.]]"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of VLDB","author":"Gyssens M.","year":"1997","unstructured":"Gyssens , M. and Lakshmanan , L . 1997. A foundation for multi-dimensional databases . In Proceedings of VLDB 1997 . 106--115.]] Gyssens, M. and Lakshmanan, L. 1997. A foundation for multi-dimensional databases. In Proceedings of VLDB 1997. 106--115.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214501753168398"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543636"},{"key":"e_1_2_1_11_1","volume-title":"Optimization Algorithms for Simultaneous Multidimensional Queries in OLAP Environments. Lecture Notes in Computer Science","volume":"2114","author":"Kalnis P.","unstructured":"Kalnis , P. and Papadias , D . 2001 . Optimization Algorithms for Simultaneous Multidimensional Queries in OLAP Environments. Lecture Notes in Computer Science , vol. 2114 . Springer-Verlag, Berlin, Germany, 264--273.]] Kalnis, P. and Papadias, D. 2001. Optimization Algorithms for Simultaneous Multidimensional Queries in OLAP Environments. Lecture Notes in Computer Science, vol. 2114. Springer-Verlag, Berlin, Germany, 264--273.]]"},{"key":"e_1_2_1_12_1","first-page":"491","article-title":"Polygon decomposition. In Handbook of Computational Geometry. Elsevier Sciences, Amsterdem, The Netherlands","volume":"11","author":"Keil J.","year":"1999","unstructured":"Keil , J. 1999 . Polygon decomposition. In Handbook of Computational Geometry. Elsevier Sciences, Amsterdem, The Netherlands , Chap. 11 , 491 -- 518 .]] Keil, J. 1999. Polygon decomposition. In Handbook of Computational Geometry. Elsevier Sciences, Amsterdem, The Netherlands, Chap. 11, 491--518.]]","journal-title":"Chap."},{"volume-title":"The Data Warehouse Toolkit","author":"Kimball R.","key":"e_1_2_1_13_1","unstructured":"Kimball , R. 1996. The Data Warehouse Toolkit . Wiley, New York , NY .]] Kimball, R. 1996. The Data Warehouse Toolkit. Wiley, New York, NY.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301369"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of VLDB","author":"Lakshmanan L.","year":"1999","unstructured":"Lakshmanan , L. , Ng , R. T. , Wang , C. X. , Zhou , X. , and Johnson , T. J . 1999. The generalized MDL approach for summarization . In Proceedings of VLDB 1999 . 445--454.]] Lakshmanan, L., Ng, R. T., Wang, C. X., Zhou, X., and Johnson, T. J. 1999. The generalized MDL approach for summarization. In Proceedings of VLDB 1999. 445--454.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1994.tb00166.x"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science","volume":"1269","author":"Levcopoulos C.","unstructured":"Levcopoulos , C. and Gudmundsson , J . 1997. Approximation algorithms for covering polygons with squares and similar problems . In Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science , vol. 1269 . Springer, Berlin, Germany, 27--41.]] Levcopoulos, C. and Gudmundsson, J. 1997. Approximation algorithms for covering polygons with squares and similar problems. In Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science. Lecture Notes in Computer Science, vol. 1269. Springer, Berlin, Germany, 27--41.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050011"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"211","DOI":"10.3233\/FI-1978-2114","article-title":"On two-dimensional data organization I","volume":"2","author":"Lodi E.","year":"1979","unstructured":"Lodi , E. , Luccio , F. , Mugnai , C. , and Pagli , L. 1979 . On two-dimensional data organization I . Fundam. Inform. 2 , 211 -- 226 .]] Lodi, E., Luccio, F., Mugnai, C., and Pagli, L. 1979. On two-dimensional data organization I. Fundam. Inform. 2, 211--226.]]","journal-title":"Fundam. Inform."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of ICDE","author":"Park C.","year":"2001","unstructured":"Park , C. , Kim , M. , and Lee , Y . 2001. Rewriting OLAP queries using materialized views and dimension hierarchies in data warehouses . In Proceedings of ICDE 2001 . 515--523.]] Park, C., Kim, M., and Lee, Y. 2001. Rewriting OLAP queries using materialized views and dimension hierarchies in data warehouses. In Proceedings of ICDE 2001. 515--523.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/357346.357348"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276329"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1061318.1061324","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1061318.1061324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:36:56Z","timestamp":1750282616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1061318.1061324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1145\/1061318.1061324"],"URL":"https:\/\/doi.org\/10.1145\/1061318.1061324","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2005,3]]},"assertion":[{"value":"2005-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}