UBC Theses and Dissertations
Quotient cube and QC-tree : efficient summarizations for semantic OLAP Zhao, Yan
Most data cube compression approaches focused on reducing the cube size but overlooked preserving the semantics of data cubes. A technique called quotient cube was proposed recently as a summary structure for a data cube that retains its semantics. It can be constructed very efficiently and it leads to a significant reduction in the cube size. However, many issues have not been addressed regarding the application of quotient cubes. For instance, efficient storage and index structures were not provided; No specific algorithm for query answering was given; Incremental maintenance against updates was not discussed. In this thesis work, we are aiming at developing proper solutions to the above problems. Firstly, we introduce the idea of sorted list to index quotient cubes and provide associated query answering algorithms. Secondly, since a tabular representation with additional index is neither compact nor efficient to maintain, we propose a more efficient data structure called QC-tree to store and index quotient cubes. We present a depth-first search based algorithm for constructing QC-trees directly from base tables. Thirdly, we devise efficient algorithms for answering various queries and incrementally maintaining QCtrees against base table updates. An extensive experimental study illustrates the space and time savings achieved by our algorithms. Finally, we implement a quotient cube based data warehouse system to demonstrate our research accomplishments.
Item Citations and Data