An Effective Heuristic for Multi-dimensional Partitioning in Bottom-Up Computation for Data Cubes

Bottom-Up Computation (BUC) is one of the most studied algorithms for data cube generation in on-line analytical processing. Its computation in the bottom up style allows the algorithm to efficiently generate a data cube for input data that can fit into the memory.When the entire input data cannot fit into the memory,many sources in literature suggest partitioning the data by a dimension and then running the algorithm on each of the single-dimensional partitioned data to generate a data cube. For very large sized input data,the partitioned data might still not be able to fit into the memory and partitioning by additional dimensions is required. However, this multi-dimensional partitioning is more complicated than single dimensional partitioning and it has not been fully discussed before. Our goal is to provide an effective heuristic implementation on multi-dimensional partitioning in BUC.