Cubetree: organization of and bulk incremental updates on the data cube

ABSTRACT

The data cube is an aggregate operator which has been shown to be very powerful for On Line Analytical Processing (OLAP) in the context of data warehousing. It is, however, very expensive to compute, access, and maintain. In this paper we define the “cubetree” as a storage abstraction of the cube and realize in using packed R-trees for most efficient cube queries. We then reduce the problem of creation and maintenance of the cube to sorting and bulk incremental merge-packing of cubetrees. This merge-pack has been implemented to use separate storage for writing the updated cubetrees, therefore allowing cube queries to continue even during maintenance. Finally, we characterize the size of the delta increment for achieving good bulk update schedules for the cube. The paper includes experiments with various data sets measuring query and bulk update performance.

REFERENCES

• AAD+96: 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
• BM72: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta In. formatica, 1(3):173-189, 1972.
• GBLP96: 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
• GHRU97: Himanshu Gupta , Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Index Selection for OLAP, Proceedings of the Thirteenth International Conference on Data Engineering, p.208-219, April 07-11, 1997
• Gra93: Jim Gray, Benchmark Handbook: For Database and Transaction Processing Systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• GSE+94: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• Gut84: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• HRU96: 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
• KF93: Ibrahim Kamel and Christos Faloutsos. Hflbert r-tree: an improved r-tree using fraztals. Systems Research Center (SRC) TR-93-19, Univ. of Maryland, College Park, 1993.
• NBC+94: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a RISC machine sort, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.233-242, May 24-27, 1994, Minneapolis, Minnesota, United States
• RL85: Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
• Rou82: Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
• SDNR96: Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton , Karthikeyan Ramasamy, Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies, Proceedings of the 22th International Conference on Very Large Data Bases, p.522-531, September 03-06, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Design, Experimentation, Management, Measurement, Performance, Theory