Iceberg-cube computation with PC clusters

In this paper, we investigate the approach of using low cost PC dusters to parallelize the computation of iceberg-cube queries. We concentrate on tech niques directed towards online querying of large, high-dimensional datasets where it is assumed that the total cube has not been precomputed. The algo rithmic space we explore considers trade-offs between parallelism, computat ion and I/O, Our main contribution is the development and a comprehensive e valuation of various novel, parallel algorithms. Specifically: (1) Algorith m RP is a straightforward parallel version of BUC [BR99]; (2) Algorithm BPP attempts to reduce I/O 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, Algor ithm PT load-balances by using binary partitioning to divide the cube latti ce as evenly as possible. We present a thorough performance evaluation on all these algorithms on a v ariety of parameters, including the dimensionality of the cube, the sparsen ess of the cube, the selectivity of the constraints, the number of processo rs, and the size of the dataset. A key finding is that it is not a one-algo rithm-fit-all situation. We recommend a "recipe" which uses PT as the defau lt algorithm, but may also deploy ASL under specific circumstances.