Concise descriptions of subsets of structured sets

ABSTRACT

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 U, and a language L whose expressions define subsets of U, the problem of minimum description length in L (L-MDL) is: “given a subset V of U, find a shortest string in L that defines V.” 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.

REFERENCES

• 1: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 2: Rakesh Agrawal , Ashish Gupta , Sunita Sarawagi, Modeling Multidimensional Databases, Proceedings of the Thirteenth International Conference on Data Engineering, p.232-243, April 07-11, 1997
• 3: Batchelor, B. 1980. Hierarchical shape description based on convex hulls of concavities. J. Cybernet. 10, 205--210.
• 4: Luca Cabibbo , Riccardo Torlone, Querying Multidimensional Databases, Proceedings of the 6th International Workshop on Database Programming Languages, p.319-335, August 18-20, 1997
• 5: Luca Cabibbo , Riccardo Torlone, A Logical Approach to Multidimensional Databases, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.183-197, March 23-27, 1998
• 6: Jeff Edmonds , Jarek Gryz , Dongming Liang , Renée J. Miller, Mining for Empty Rectangles in Large Data Sets, Proceedings of the 8th International Conference on Database Theory, p.174-188, January 04-06, 2001
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: Marc Gyssens , Laks V. S. Lakshmanan, A Foundation for Multi-dimensional Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.106-115, August 25-29, 1997
• 9: Hansen, M. H. and Yu, B. 2001. Model selection and the principle of minimum description length. J. Amer. Statist. Assoc. 96, 454, 746--774.
• 10: Carlos A. Hurtado , Alberto O. Mendelzon, OLAP dimension constraints, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543636]
• 11: Panos Kalnis , Dimitris Papadias, Optimization Algorithms for Simultaneous Multidimensional Queries in OLAP Environments, Proceedings of the Third International Conference on Data Warehousing and Knowledge Discovery, p.264-273, September 05-07, 2001
• 12: Keil, J. 1999. Polygon decomposition. In Handbook of Computational Geometry. Elsevier Sciences, Amsterdem, The Netherlands, Chap. 11, 491--518.
• 13: Kimball, R. 1996. The Data Warehouse Toolkit. Wiley, New York, NY.
• 14: V. S. Anil Kumar , H. Ramesh, Covering rectilinear polygons with axis-parallel rectangles, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.445-454, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301369]
• 15: 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.
• 16: Lam, W. and Bacchus, F. 1994. Learning Bayesian belief networks: An approach based on the MDL principle. Comput. Intel. 10, 269--293.
• 17: Christos Levcopoulos , Joachim Gudmundsson, Approximation Algorithms for Covering Polygons with Squares and Similar Problems, Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, p.27-41, July 11-12, 1997
• 18: Weifa Liang , Maria E. Orlowska , Jeffrey X. Yu, Optimizing multiple dimensional queries simultaneously in multidimensional databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.319-338, February 2000 [doi>10.1007/s007780050011]
• 19: Lodi, E., Luccio, F., Mugnai, C., and Pagli, L. 1979. On two-dimensional data organization I. Fundam. Inform. 2, 211--226.
• 20: Chang-Sup Park , Myoung-Ho Kim , Yoon-Joon Lee, Rewriting OLAP Queries Using Materialized Views and Dimension Hierarchies in Data Warehouses, Proceedings of the 17th International Conference on Data Engineering, p.515-523, April 02-06, 2001
• 21: S. B. Tor , A. E. Middleditch, Convex Decomposition of Simple Polygons, ACM Transactions on Graphics (TOG), v.3 n.4, p.244-265, Oct. 1984 [doi>10.1145/357346.357348]
• 22: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton , Amit Shukla, Simultaneous optimization and evaluation of multiple dimensional queries, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.271-282, June 01-04, 1998, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms
      H.2.3 Languages

General Terms:
Algorithms, Theory

Keywords:
Minimal description length, OLAP, query optimization, summarization