Star-Cubing: Computing Iceberg Cubes by Top-Down and Bottom-Up Integration Dong Xin, Jiawei Han, Xiaolei Li, and Benjamin W. Wah   View Paper (PDF)   Return to OLAP & Data Mining (Session B3) Abstract , computes the iceberg cube bottom-up and facilitates Apriori prun- ing. BUC explores fast sorting and partition- ing techniques; whereas H-Cubing explores a data structure, H-Tree, for shared computa- tion. However, none of them fully explores multi-dimensional simultaneous aggregation. In this paper, we present a new method, Star- Cubing, that integrates the strengths of the previous three algorithms and performs ag- gregations on multiple dimensions simultane- ously. It utilizes a star-tree structure, ex- tends the simultaneous aggregation methods, and enables the pruning of the group-by's that do not satisfy the iceberg condition. Our performance study shows that Star-Cubing is highly efficient and outperforms all the previ- ous methods in almost all kinds of data distri- butions. ©2004 Association for Computing Machinery