- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Iceberg-cube computation with PC cluster
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Iceberg-cube computation with PC cluster Yin, Yu
Abstract
Iceberg queries constitute one of the most important classes of queries for OLAP applications. This thesis investigates using low cost PC clusters to parallelize the computation of iceberg queries. We concentrate on techniques for querying large, high-dimensional data sets. Our exploration of an algorithmic space considers tradeoffs between parallelism, compuation, memory and I/O. The main contribution of this thesis is the development and evaluation of various novel, parallel algorithms for CUBE computation and online aggregation. These include the following: one, the CUBE Algorithm RP, which is a straightforward parallel version of BUC[BR99]; two, the CUBE Algorithm BPP, which attempts to reduce I/O by outputting results in a more efficient way; three, the CUBE Algorithms ASL and AHT, which maintain cells in a cuboid in a skip list and a hash table respectively, designed to put the utmost priority on load balancing; four, alternatively, the CUBE Algorithm PT load-balances by using binary partitioning to divide the cube lattice as evenly as possible; and five, the online aggregating algorithm POL, based on ASL and sampling technique, which gives back instant response and further progressive refinement. We present a thorough performance evaluation of all these algorithms in a variety of parameters, including the dimensionality and the sparseness the cube, the selectivity of the constraints, the number of processors, and the size of the data set. The key to understanding the CUBE algorithms is in that one-algorithm-does-not-fit- all. We recommend a "recipe" which uses PT as the default algorithm, but may also deploy ASL or AHT in appropriate circumstances. The online aggregation algorithm, POL, is especially suitable for computing a high dimensional query over a large data set with a cluster of machines connected by high speed networks.
Item Metadata
Title |
Iceberg-cube computation with PC cluster
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2001
|
Description |
Iceberg queries constitute one of the most important classes of queries for OLAP
applications. This thesis investigates using low cost PC clusters to parallelize the
computation of iceberg queries. We concentrate on techniques for querying large,
high-dimensional data sets. Our exploration of an algorithmic space considers tradeoffs
between parallelism, compuation, memory and I/O. The main contribution of
this thesis is the development and evaluation of various novel, parallel algorithms
for CUBE computation and online aggregation. These include the following: one,
the CUBE Algorithm RP, which is a straightforward parallel version of BUC[BR99];
two, the CUBE Algorithm BPP, which attempts to reduce I/O by outputting results
in a more efficient way; three, the CUBE Algorithms ASL and AHT, which
maintain cells in a cuboid in a skip list and a hash table respectively, designed
to put the utmost priority on load balancing; four, alternatively, the CUBE Algorithm
PT load-balances by using binary partitioning to divide the cube lattice as
evenly as possible; and five, the online aggregating algorithm POL, based on ASL
and sampling technique, which gives back instant response and further progressive
refinement.
We present a thorough performance evaluation of all these algorithms in a
variety of parameters, including the dimensionality and the sparseness the cube, the
selectivity of the constraints, the number of processors, and the size of the data set.
The key to understanding the CUBE algorithms is in that one-algorithm-does-not-fit-
all. We recommend a "recipe" which uses PT as the default algorithm, but may
also deploy ASL or AHT in appropriate circumstances. The online aggregation
algorithm, POL, is especially suitable for computing a high dimensional query over
a large data set with a cluster of machines connected by high speed networks.
|
Extent |
3487410 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-08-06
|
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.0051672
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2001-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.