Algorithms and Architectures for Parallel Processing / Lecture Notes in Computer Science Bd.4494 (PDF)

access forms such as OLAP (on-line analytical processing), data mining, etc. OLAP refers to the technologies that allow users to efficiently retrieve data from the data warehouse for decision support purposes [1]. A lot of research has been done in order to improve the OLAP query performance and to provide fast response times for queries on large data warehouses. Efficient indexing [2], materialization [3] and data cubing [4] are common techniques to speed up the OLAP query processing. Many efficient cube computation algorithms have been proposed recently, such as BUC [5], H-cubing [6], Quotient cubing [7], and Starcubing [8]. However, in the large data warehouse applications, such as bioinformatics, the data usually has high dimensionality with more than 100 dimensions. Since data cube grows exponentially with the number of dimensions, it is generally too costly in both computation time and storage space to materialize a full high-dimensional data cube. For example, a data cube of 100 dimensions, each with 100 distinct values, may contain as many as 101100 cells. If we consider the dimension hierarchies, the aggregate cell will increase even more tremendously. Although condensed cube [9], dwarf cube [10], or star cubes [8] can delay the explosion, it does not solve the fundamental problem [11]. The minimal cubing approach from Li and Han [11] can alleviate this problem, but does not consider the dimension hierarchies and cannot efficiently handle OLAP queries. In this paper, we develop a feasible parallel hierarchical cubing algorithm (PHC) that supports dimension hierarchies for highdimensional data cubes and answers OLAP queries efficiently. The algorithm decomposes a multi-dimensional hierarchical data cube into smaller cube segments. This proposed data allocation and processing model supports parallel I/O and parallel processing as well as load balancing for disks and processors. This proposed cubing algorithm is an efficient and scalable parallel processing algorithm for cube computation.