The multi-tree cubing algorithm for computing iceberg cubes.

摘要

The computation of data cubes is one of the major operations in on-line analytical processing (OLAP), but it is also one of the most expensive. To improve efficiency, an iceberg cube represents only the cells whose aggregate value is above a given threshold (minimum support). Two existing approaches, top-down and bottom-up, are used to compute the iceberg cube for a data set, but both have performance limitations.; In this thesis, a new algorithm, called Multi-Tree Cubing (MTC), is proposed and implemented for computing an iceberg cube. Overall, the Multi-Tree Cubing algorithm is a top-down approach, so it features shared computation. By processing the orderings in the opposite order from a top-down approach called Top-Down Computation, the MTC algorithm is able to prune attributes at the partition level, which is more accurate than the pruning in a bottom-up approach called Bottom-Up Computation (BUC). The MTC algorithm is based on a specialized type of prefix tree data structure, called a AP-tree, which facilitates fast sorting and Apriori-like pruning. Once a tree is constructed, MTC traverses the tree in a depth-first manner and checks each partition against the minimum support to determine if it should output a result or prune the current branch. The results of five series of experiments comparing MTC versus BUC on real and synthetic databases are presented. The experimental results showed that MTC consistently performed the same as or better than BUC for all five series of experiments.