BUC algorithm for iceberg cubes

Abstract

The Iceberg-Cube problem restricts the computation of the data cube to only those group-by partitions satisfying a minimum threshold condition defined on a specified measure. In this paper, we implement the Bottom-Up Computation (BUC) algorithm for computing Iceberg cubes and conduct a sensitivity analysis of BUC with respect to the probability density function of the data. The distributions under consideration are the Gaussian, Geometric, and Poisson distributions. The Uniform distribution is used as a basis for comparison. Results show that when the cube is sparse there is a correlation between the data distribution and the running time of the algorithm. In particular, BUC performs better on Uniform followed by Poisson, Gaussian and Geometric data.