QC-trees: an efficient summary structure for semantic OLAP

ABSTRACT

Recently, a technique called quotient cube was proposed as a summary structure for a data cube that preserves its semantics, with applications for online exploration and visualization. The authors showed that a quotient cube can be constructed very efficiently and it leads to a significant reduction in the cube size. While it is an interesting proposal, that paper leaves many issues unaddressed. Firstly, a direct representation of a quotient cube is not as compact as possible and thus still wastes space. Secondly, while a quotient cube can in principle be used for answering queries, no specific algorithms were given in the paper. Thirdly, maintaining any summary structure incrementally against updates is an important task, a topic not addressed there. In this paper, we propose an efficient data structure called QC-tree and an efficient algorithm for directly constructing it from a base table, solving the first problem. We give efficient algorithms that address the remaining questions. We report results from an extensive performance study that illustrate the space and time savings achieved by our algorithms over previous ones (wherever they exist).

REFERENCES

• 1: Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
• 2: Andrey Balmin , Thanos Papadimitriou , Yannis Papakonstantinou, Hypothetical Queries in an OLAP Environment, Proceedings of the 26th International Conference on Very Large Data Bases, p.220-231, September 10-14, 2000
• 3: Daniel Barbará , Mark Sullivan, Quasi-cubes: exploiting approximations in multidimensional databases, ACM SIGMOD Record, v.26 n.3, p.12-17, Sept. 1997 [doi>10.1145/262762.262764]
• 4: Daniel Barbará , Xintao Wu, Using Loglinear Models to Compress Datacube, Proceedings of the First International Conference on Web-Age Information Management, p.311-322, June 21-23, 2000
• 5: Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: C. Carpineto and G. Romano:. Galois: An order-theoretic approach to conceptual clustering. In ICML'93.
• 7: Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303992]
• 8: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 9: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 10: C.Hahn et al. Edited synoptic cloud reports from ships and land stations over the globe, 1982--1991. cdiac.est.ornl.gov/ftp/ndp026b/SEP85L.Z, 1994.
• 11: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 12: C. A. Hurtado et al. Maintaining data cubes under dimension updates. In ICDE'99.
• 13: Carlos A. Hurtado , Alberto O. Mendelzon , Alejandro A. Vaisman, Updating OLAP dimensions, Proceedings of the 2nd ACM international workshop on Data warehousing and OLAP, p.60-66, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319757.319791]
• 14: L. V. S. Lakshmanan et al. Quotient cube: How to summarize the semantics of a data cube. In VLDB'02.
• 15: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 16: Alberto O. Mendelzon , Alejandro A. Vaisman, Temporal Queries in OLAP, Proceedings of the 26th International Conference on Very Large Data Bases, p.242-253, September 10-14, 2000
• 17: Inderpal Singh Mumick , Dallan Quass , Barinderpal Singh Mumick, Maintenance of data cubes and summary tables in a warehouse, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.100-111, May 11-15, 1997, Tucson, Arizona, United States
• 18: Dallan Quass , Ashish Gupta , Inderpal Singh Mumick , Jennifer Widom, Making views self-maintainable for data warehousing, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.158-169, December 18-20, 1996, Miami Beach, Florida, United States
• 19: Dallan Quass , Jennifer Widom, On-line warehouse view maintenance, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.393-404, May 11-15, 1997, Tucson, Arizona, United States
• 20: Kenneth A. Ross , Divesh Srivastava, Fast Computation of Sparse Datacubes, Proceedings of the 23rd International Conference on Very Large Data Bases, p.116-125, August 25-29, 1997
• 21: Nick Roussopoulos , Yannis Kotidis , Mema Roussopoulos, Cubetree: organization of and bulk incremental updates on the data cube, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.89-99, May 11-15, 1997, Tucson, Arizona, United States
• 22: S. Sarawagi. Indexing OLAP data. IEEE Data Eng. Bulletin, 20:36--43, 1997.
• 23: Gayatri Sathe , Sunita Sarawagi, Intelligent Rollups in Multidimensional OLAP Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.531-540, September 11-14, 2001
• 24: Jayavel Shanmugasundaram , Usama Fayyad , P. S. Bradley, Compressed data cubes for OLAP aggregate query approximation on continuous dimensions, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.223-232, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312231]
• 25: Yannis Sismanis , Antonios Deligiannakis , Nick Roussopoulos , Yannis Kotidis, Dwarf: shrinking the PetaCube, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564745]
• 26: Jeffrey Scott Vitter , Min Wang , Bala Iyer, Data cube approximation and histograms via wavelets, Proceedings of the seventh international conference on Information and knowledge management, p.96-104, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288645]
• 27: W. Wang et al. Condensed cube: An effective approach to reducing data cube size. In ICDE'02.
• 28: Jun Yang , Jennifer Widom, Maintaining Temporal Views over Non-Temporal Information Sources for Data Warehousing, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.389-403, March 23-27, 1998
• 29: Jun Yang , Jennifer Widom, Temporal View Self-Maintenance, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.395-412, March 27-31, 2000
• 30: Yihong Zhao , Prasad M. Deshpande , Jeffrey F. Naughton, An array-based algorithm for simultaneous multidimensional aggregates, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.159-170, May 11-15, 1997, Tucson, Arizona, 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.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Performance