In this paper, we investigate the approach of using low cost PC clusters 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 not 
been precomputed. The algorithmic space we explore considers trade-offs between parallelism, 
computation and I/O. 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/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, 
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.