- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Quotient cube and QC-tree : efficient summarizations...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Quotient cube and QC-tree : efficient summarizations for semantic OLAP Zhao, Yan
Abstract
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 Metadata
Title |
Quotient cube and QC-tree : efficient summarizations for semantic OLAP
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2003
|
Description |
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.
|
Extent |
4564360 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-10-31
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
|
DOI |
10.14288/1.0051454
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2003-11
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.