Iceberg-cube computation with PC clusters

ABSTRACT

In this paper, we investigate the approach of using low cost PC cluster to parallelize the computation of iceberg-cube queries. We concentrate on techniques directed towards online querying of large, high-dimensional datasets where it is assumed that the total cube has net been precomputed. The algorithmic space we explore considers trade-offs between parallelism, computation and I/0. Our main contribution is the development and a comprehensive evaluation of various novel, parallel algorithms. Specifically: (1) Algorithm RP is a straightforward parallel version of BUC [BR99]; (2) Algorithm BPP attempts to reduce I/0 by outputting results in a more efficient way; (3) Algorithm ASL, which maintains cells in a cuboid in a skiplist, is designed to put the utmost priority on load balancing; and (4) alternatively, Algorithm PT load-balances by using binary partitioning to divide the cube lattice as evenly as possible.

We present a thorough performance evaluation on all these algorithms on a variety of parameters, including the dimensionality of the cube, the sparseness of the cube, the selectivity of the constraints, the number of processors, and the size of the dataset. A key finding is that it is not a one-algorithm-fit-all situation. We recommend a “recipe” which uses PT as the default algorithm, but may also deploy ASL under specific circumstances.

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: Elena Baralis , Stefano Paraboschi , Ernest Teniente, Materialized Views Selection in a Multidimensional Database, Proceedings of the 23rd International Conference on Very Large Data Bases, p.156-165, August 25-29, 1997
• 3: 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
• 4: Michael Eberl , Wolfgang Karl , Carsten Trinitis , Andreas Blaszczyk, Parallel Computing on PC Clusters - An Alternative to Supercomputers for Industrial Applications, Proceedings of the 6th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.493-498, September 26-29, 1999
• 5: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 6: Sanjay Goil , Alok Choudhary, High Performance OLAP and Data Mining on Parallel Computers, Data Mining and Knowledge Discovery, v.1 n.4, p.391-417, December 1997 [doi>10.1023/A:1009777418785]
• 7: 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
• 8: 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
• 9: 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
• 10: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 11: M. Kamber, J. Han and J. Chiang. Metarule-guided mining of multi-dimensional association rules using data cubes. In Proc. 1997 KDD, pp. 207-210.
• 12: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 13: 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
• 14: Sunita Sarawagi, Explaining Differences in Multidimensional Aggregates, Proceedings of the 25th International Conference on Very Large Data Bases, p.42-53, September 07-10, 1999
• 15: Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton, Materialized View Selection for Multidimensional Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.488-499, August 24-27, 1998
• 16: Anurag Srivastava , Eui-Hong Han , Vipin Kumar , Vineet Singh, Parallel Formulations of Decision-Tree Classification Algorithms, Data Mining and Knowledge Discovery, v.3 n.3, p.237-261, September 1999 [doi>10.1023/A:1009832825273]
• 17: Masahisa Tamura , Masaru Kitsuregawa, Dynamic Load Balancing for Parallel Association Rule Mining on Heterogenous PC Cluster Systems, Proceedings of the 25th International Conference on Very Large Data Bases, p.162-173, September 07-10, 1999
• 18: Mohammed J. Zaki, Parallel and Distributed Association Mining: A Survey, IEEE Concurrency, v.7 n.4, p.14-25, October 1999 [doi>10.1109/4434.806975]
• 19: 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.7 Database Administration
          Subjects: Data warehouse and repository

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

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

Keywords:
OLAP, parallel computation