Parallelizing the Data Cube.
This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms. We describe two different partitioning strategies, one for top-down and one for bottom-up cube algorithms. Both partitioning strategies assign subcubes to individual processors in such a way that the loads assigned to the processors are balanced. Our methods reduce inter processor communication overhead by partitioning the load in advance instead of computing each individual group-by in parallel. Our partitioning strategies create a small number of coarse tasks. This allows for sharing of prefixes and sort orders between different group-by computations. Our methods enable code reuse by permitting the use of existing sequential (external memory) data cube algorithms for the subcube computations on each processor. This supports the transfer of optimized sequential data cube code to a parallel setting.The bottom-up partitioning strategy balances the number of single attribute external memory sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated group-by sizes. Both partitioning approaches can be implemented on any shared disk type parallel machine composed of p processors connected via an interconnection fabric and with access to a shared parallel disk array.We have implemented our parallel top-down data cube construction method in C++ with the MPI message passing library for communication and the LEDA library for the required graph algorithms. We tested our code on an eight processor cluster, using a variety of different data sets with a range of sizes, dimensions, density, and skew. Comparison tests were performed on a SunFire 6800. The tests show that our partitioning strategies generate a close to optimal load balance between processors. The actual run times observed show an optimal speedup of p.
Figure

1. A 4-dimensional lattice.
is aggregated over all distinct combinations over AB. A group-by is a child of some parent
group-by if the child can be computed from the parent by aggregating some of its
attributes. Parent-child relationships allow algorithms to share partitions, sorts, and partial
sorts between different group-buys. For example, if the data has been sorted with respect
to AB, then cuboid group-by A can be generated from AB without sorting and generating
ABC requires only a sorting of blocks of entries. Cube algorithms differ on how they make
use of these commonalities. Bottom-up approaches reuse previously computed sort orders
and generate more detailed group-buys from less detailed ones (a less detailed group-by
contains a subset of the attributes). Top-down approaches use more detailed group-bys
to compute less detailed ones. Bottom-up approaches are better suited for sparse rela-
tions. Relation R is sparse if N is much smaller than the number of possible values in
the given d-dimensional space. We present different partitioning and load balancing approaches
depending on whether a top-down or bottom-up sequential cube algorithm is
used.
We conclude this section with a brief discussion of the underlying parallel model, the
standard shared disk parallel machine model. That is, we assume p processors connected
via an interconnection fabric where processors have typical workstation size local memories
and concurrent access to a shared disk array. For the purpose of parallel algorithm design,
we use the Coarse Grained Multicomputer (CGM) model [5, 8, 15, 18, 27]. More precisely,
we use the EM-CGM model [6, 7, 9] which is a multi-processor version of Vitter's Parallel
Model [28?30]. For our parallel data cube construction methods we assume that the
d-dimensional input data set R of size N is stored on the shared disk array. The output, i.e.
the group-bys comprising the data cube, will be written to the shared disk array. Subsequent
applications may impose requirements on the output. For example, a visualization application
may require storing group-by in striped format over the entire disk array to support
fast access to individual group-bys.
3. Parallel bottom-up data cube construction
Bottom-up data cube construction methods calculate the group-bys in an order which emphasizes
the reuse of previously computed sorts and they generate more detailed group-buys
from less detailed ones. Bottom-up methods are well suited for sparse relations and they
support the selective computation of blocks in a group-by; e.g., generate only blocks which
specify a user-de?ned aggregate condition [4].
Previous bottom-up methods include BUC [4] and PartitionCube (part of [24]). The main
idea underlying bottom-up methods can be captured as follows: if the data has previously
been sorted by attribute A, then creating an AB sort order does not require a complete
resorting. A local resorting of A-blocks (blocks of consecutive elements that have the same
attribute can be used instead. The sorting of such A-blocks can often be performed in local
memory. Hence, instead of another external memory sort, the AB order can be created in one
single scan through the disk. Bottom-up methods [4, 24] attempt to break the problem into
a sequence of single attribute sorts which share pre?xes of attributes and can be performed
in local memory with a single disk scan. As outlined in [4, 24], the total computation time
of these methods is dominated by the number of such single attribute sorts.
In this section we describe a partitioning of the group-by computations into p independent
subproblems. The partitioning generates subproblems which can be processed ef?ciently by
bottom-up sequential cube methods. The goal of the partitioning is to balance the number of
single attribute sorts required by each subproblem and to ensure that each subproblem has
overlapping sort sequences in the same way as for the sequential methods (thereby avoiding
additional work).
Let A1,.,Ad be the attributes of relation R and assume |A1|?|A2|, ???|Ad|
where |Ai | is the number of different possible values for attribute Ai . As observed in [24],
the set of all groups-bys of the data cube can be partitioned into those that contain A1 and
those that do not contain A1. In our partitioning approach, the groups-bys containing A1 will
be sorted by A1. We indicate this by saying that they contain A1 as a pre?x. The group-bys
not containing A1 (i.e., A1 is projected out) contain A1 as a post?x. We then recurse with
the same scheme on the remaining attributes. We shall utilize this property to partition the
computation of all group-bys into independent subproblems. The load between subproblems
will be balanced and they will have overlapping sort sequences in the same way as for the
sequential methods. In the following we give the details of our partitioning method.
Let x, y, z be sequences of attributes representing sort orders and let A be an arbitrary
single attribute. We introduce the following de?nition of sets of attribute sequences
representing sort orders (and their respective group-bys):
The entire data cube construction corresponds to the set Sd(?, A1 .Ad, ?) of sort orders
and respective group-bys, where d is the dimension of the the data cube. We refer
to i as the rank of Si (. The set Sd(?, A1 .Ad, ?) is the union of two subsets of
These, in turn, are the

Figure

2. Partitioning for a 4-dimensional data cube with attributes A, B, C, D. The 8 S1-sets correspond to the
group-buys determined for four attributes.
union of four subsets of rank d ? 2: Sd?2(A1 A2, A3 .Ad, ?), Sd?2(A1, A3 .Ad, A2),
Sd?2(A2, A3 .Ad, A1), and Sd?2(?, A3 .Ad, A2 A1). A complete example for a
4-dimensional data cube with attributes A, B, C, D is shown in ?gure 2.
For the sake of simplifying the discussion, we assume that p is a power of 2,
Consider the 2pS-sets of rank d these 2p sets in
the order de?ned by Eq. (2). De?ne
Our partitioning assigns set summarized
in Algorithm 1.
ALGORITHM 1. Parallel Bottom-Up Cube Construction.
Each processor Pi ,1? i ? p, performs the following steps, independently and in
parallel:
(1) Determine the two sets forming i as described below.
(2) Compute all group-bys in i using a sequential (external-memory) bottom-up
cube construction method.
?End of Algorithm?
We illustrate the partitioning using an example with 8. For these
values, we generate 16 S-sets of rank 6. Giving only the indices of attributes A1, A2, A3,

Figure

3. -sets assigned to 8 processors when represents a projected-out attribute and
? represents an existing attribute.
and A4,wehave
Each processor is assigned the computation of 27 group-bys as shown in ?gure 3. If every
processor has access to its own copy of relation R, then a processor performs
attribute sorts to generate the data in the ordering needed for its group-bys. If there is only
one copy of R, read-con?icts can be avoided by sorting the sequences using a binomial
heap broadcast pattern [19]. Doing so results in every processor Pi receiving its two sorted
sequences forming i after the time needed for single attribute sorts. Figure 4 shows
the sequence of sorts for the 8-processor example. The index inside the circles indicates the
processor assignment; i.e., processor 1 performs a total of four single attribute sorts on the
original relation R, starting with the sort on attribute A1. Using binomial heap properties, it
follows that a processor does at most k +1 single attribute sorts and the 2p sorted sequences
are available after the time needed for

Figure

4. Binomial heap structure for generating the 2p Gamma-sets without read con?icts.
Algorithm 1 can easily be generalized to values of p which are not powers of 2. We also
note that Algorithm 1 requires p ? 2d?1. This is usually the case in practice. However, if
a parallel algorithm is needed for larger values of p, the partitioning strategy needs to be
augmented. Such an augmentation could, for example, be a partitioning strategy based on
the number of data items for a particular attribute. This would be applied after partitioning
based on the number of attributes has been done. Since the range p ?{20 .2d?1} covers
current needs with respect to machine and dimension sizes, we do not further discuss such
augmentations in this paper.
The following four properties summarize the main features of Algorithm 1 that make it
load balanced and communication ef?cient:
? The computation of each group-by is assigned to a unique processor.
? The calculation of the group-bys in i , assigned to processor Pi , requires the same
number of single attribute sorts for all 1
? The sorts performed at processor Pi share pre?xes of attributes in the same way as in
[4, 24] and can be performed with disk scans in the same manner as in [4, 24].
? The algorithm requires no inter-processor communication.
4. Parallel top-down data cube construction
Top-down approaches for computing the data cube, like the sequential PipeSort, Pipe Hash,
and Overlap methods [1, 10, 25], use more detailed group-bys to compute less detailed ones
that contain a subset of the attributes of the former. They apply to data sets where the number
of data items in a group-by can shrink considerably as the number of attributes decreases
(data reduction). The PipeSort, PipeHash, and Overlap methods select a spanning tree T
of the lattice, rooted at the group-by containing all attributes. PipeSort considers two cases
of parent-child relationships. If the ordered attributes of the child are a pre?x of the ordered
attributes of the parent (e.g., ABCD ? ABC) then a simple scan is suf?cient to create
the child from the parent. Otherwise, a sort is required to create the child. PipeSort seeks
to minimize the total computation cost by computing minimum cost matchings between
successive layers of the lattice. PipeHash uses hash tables instead of sorting. Overlap
attempts to reduce sort time by utilizing the fact that overlapping sort orders do not always
require a complete new sort. For example, the ABC group-by has A partitions that can be
sorted independently on C to produce the AC sort order. This may permit independent sorts
in memory rather than always using external memory sort.
Next, we outline a partitioning approach which generates p independent subproblems,
each of which can be solved by one processor using an existing external-memory top-down
cube algorithm. The ?rst step of our algorithm determines a spanning tree T of the lattice by
using one of the existing approaches like PipeSort, PipeHash, and Overlap, respectively.
To balance the load between the different processors we next perform a storage estimation
to determine approximate sizes of the group-bys in T . This can be done, for example,
by using methods described in [11, 26]. We now work with a weighted tree. The most
crucial part of our solution is the partitioning of the tree. The partitioning of T into subtrees
induces a partitioning of the data cube problem into p subproblems (subsets of group-bys).
Determining an optimal partitioning of the weighted tree is easily shown to be an NP-complete
problem (by making, for example, a reduction to processor scheduling). Since the
weights of the tree represent estimates, a heuristic approach which generates p subproblems
with ?some control? over the sizes of the subproblems holds the most promise. While we
want the sizes of the p subproblems balanced, we also want to minimize the number of
subtrees assigned to a processor. Every subtree may require a scanning of the entire data set
R and thus too many subtrees can result in poor I/O performance. The solution we develop
balances these two considerations.
Our heuristics makes use of a related partitioning problem on trees for which ef?cient
algorithms exist, the min-max tree k-partitioning problem [3] de?ned as follows: Given a
tree T with n vertices and a positive weight assigned to each vertex, delete k edges in the
tree such that the largest total weight of a resulting subtree is minimized.
The min-max tree k-partitioning problem has been studied in [3, 12, 23]. These methods
assume that the weights are ?xed. Note that, our partitioning problem on T is different
in that, as we cut a subtree T out of T , an additional cost is introduced because the
group-by associated with the root of T must now be computed from scratch through a
separate sort. Hence, when cutting T out of T , the weight of the root of T has to be
increased accordingly. We have adapted the algorithm in [3] to account for the changes of
weights required. This algorithm is based on a pebble shifting scheme where k pebbles are
shifted down the tree, from the root towards the leaves, determining the cuts to be made.
In our adapted version, as cuts are made, the cost for the parent of the new partition is
adjusted to re?ect the cost of the additional sort. Its original cost is saved in a hash table
for possible future use since cuts can be moved many times before reaching their ?nal
position. In the remainder, we shall refer to this method as the modi?ed min-max tree
k-partitioning.
However, even a perfect min-max k-partitioning does not necessarily result in a partitioning
of T into subtrees of equal size, and nor does it address tradeoffs arising from the
number of subtrees assigned to a processor. We use tree-partitioning as an initial step for
our partitioning. To achieve a better distribution of the load we apply an over partitioning
strategy: instead of partitioning the tree T into p subtrees, we partition it into s ? p subtrees,
where s is an integer, s ? 1. Then, we use a ?packing heuristic? to determine which subtrees
belong to which processors, assigning s subtrees to every processor. Our packing heuristic
considers the weights of the subtrees and pairs subtrees by weights to control the number
of subtrees. It consists of s matching phases in which the p largest subtrees (or groups of
subtrees) and the p smallest subtrees (or groups of subtrees) are matched up. Details are
described in Step 2b of Algorithm 2.
ALGORITHM 2. Sequential Tree-partition(T , s, p).
Input:Aspanningtree T ofthelatticewithpositiveweightsassignedtothenodes(represent-
ing the cost to build each node from it's ancestor in T ). Integer parameters s (oversampling
ratio) and p (number of processors).
Output: A partitioning of T into p subsets 1,.,p of s subtrees each.
(1) Compute a modi?ed min-max tree s ? p-partitioning of T into s ? p subtrees T1,.,
Ts?p.
190 DEHNE ET AL.
(2) Distributesubtrees T1,.,Ts?p amongthe p subsets1,.,p,s subtreespersubset,
as follows:
(2a) Create s ? p sets of trees named ?i ,1? i ? sp, where initially ?i ={Ti }. The
weight of ?i is de?ned as the total weight of the trees in ?i .
(2b) For
? Sort the ?-sets by weight, in increasing order. W.L.O.G., let ?1,.,
?sp?(j?1)p be the resulting sequence.
?End of Algorithm?
The above tree partition algorithm is embedded into our parallel top-down data cube
construction algorithm. Our method provides a framework for parallelizing any sequential
top-down data cube algorithm. An outline of our approach is given in the following
Algorithm 3.
ALGORITHM 3. Parallel Top-Down Cube Construction.
Each processor Pi ,1?i ? p, performs the following steps independently and in
parallel:
(1) Apply the storage estimation method in [11, 26] to determine the approximate
sizes of all group-bys in T .
(2) Select a sequential top-down cube construction method (e.g., PipeSort, Pipe
Hash,orOverlap) and compute the spanning tree T of the lattice as used by
this method. Compute the weight of each node of T : the estimated cost to build
each node from it's ancestor in T .
(3) Execute Algorithm Tree-partition(T, s, p) as shown above, creating p sets
1,.,p. Each set i contains s subtrees of T .
(4) Compute all group-bys in subset i using the sequential top-down cube construction
method chosen in Step 1.
?End of Algorithm?
Our performance results described in Section 6 show that an over partitioning with
or 3 achieves very good results with respect to balancing the loads assigned to the processors.
This is an important result since a small value of s is crucial for optimizing performance.
5. Parallel array-based data cube construction
Our method in Section 4 can be easily modi?ed to obtain an ef?cient parallelization of the
ArrayCube method presented in [32]. The ArrayCube method is aimed at dense data cubes
and structures the raw data set in a d-dimensional array stored on disk as a sequence of
?chunks?. Chunking is a way to divide the d-dimensional array into small size d-dimensional
chunks where each chunk is a portion containing a data set that ?ts into a disk block. When a
?xed sequence of such chunks is stored on disk, the calculation of each group-by requires a
certain amount of buffer space [32]. The ArrayCube method calculates a minimum memory
spanning tree of group-bys, MMST, which is a spanning tree of the lattice such that the total
amount of buffer space required is minimized. The total number of disk scans required for
the computation of all group-bys is the total amount of buffer space required divided by the
memory space available. The ArrayCube method can therefore be parallelized by simply
applying Algorithm 3 with T being the MMST.
6. Experimental performance analysis
We have implemented and tested our parallel top-down data cube construction method
presented in Section 4. We implemented sequential pipesort [1] in C++, and our parallel
top-down data cube construction method (Section 4) in C++ with MPI [2]. Most of the
required graph algorithms, as well as data structures like hash tables and graph representa-
tions, were drawn from the LEDA library [21]. Still, the implementation took one person
year of full time work. We chose to implement our parallel top-down data cube construction
method rather than our parallel bottom-up data cube construction method because the
former has more tunable parameters that we wish to explore. As our primary parallel hardware
platform, we use a PC cluster consisting of a front-end machine and eight processors.
The front-end machine is used to partition the lattice and distribute the work among the
other 8 processors. The front-end machine is an IBM Net?nity server with two 9 GB SCSI
disks, 512 MB of RAM and a 550-MHZ Pentium processor. The processors are 166 MHZ
Pentiums with 2G IDE hard drives and 32 MB of RAM, except for one processor which
is a 133 MHZ Pentium. The processors run LINUX and are connected via a 100 Mbit Fast
Ethernet switch with full wire speed on all ports. Clearly, this is a very low end, older, hardware
platform. The experiments reported in the remainder of this section represent several
weeks of 24 hr/day testing and the PC cluster platform described above has the advantage
of being available exclusively for our experiments without any other user disturbing our
measurements. For our main goal of studying the speedup obtained by our parallel method
rather than absolute times, this platform proved suf?cient. To verify that our results also
hold for newer machines with faster processors, more memory per processor, and higher
bandwidth, we then ported our code to a SunFire 6800 and performed comparison tests
on the same data sets. The SunFire 6800 used is a very recent SUN multiprocessor with
Sun UltraSPARC III 750 MHz processors running Solaris 8, 24 GB of RAM and a Sun T3
shared disk.

Figure

5 shows the PC cluster running time observed as a function of the number of processors
used. For the same data set, we measured the sequential time (sequential pipesort [1])
and the parallel time obtained through our parallel top-down data cube construction method
(Section 4), using an oversampling ratio of 2. The data set consisted of 1,000,000
records with dimension 7. Our test data values were uniformly distributed over 10 values
in each dimension. Figure 5 shows the running times of the algorithm as we increase
the number of processors. There are three curves shown. The runtime curve shows the
time taken by the slowest processor (i.e. the processor that received the largest workload).
The second curve shows the average time taken by the processors. The time taken by the
front-end machine, to partition the lattice and distribute the work among the compute nodes,

Figure

5. PC cluster running time in seconds as a function of the number of processors. (Fixed parameters: Data
7. Experiments per data point = 5).
was insigni?cant. The theoretical optimum curve shown in ?gure 5 is the sequential pipesort
time divided by the number of processors used.
We observe that the runtime obtained by our code and the theoretical optimum are
essentially identical. That is, for an oversampling ratio of 2, an optimal speedup of p
is observed. (The anomaly in the runtime curve at due to the slower 133 MHZ
Pentium processor.)
Interestingly, the average time curve is always below the theoretical optimum curve, and
even the runtime curve is sometimes below the theoretical optimum curve. One would have
expected that the runtime curve would always be above the theoretical optimum curve.
We believe that this superlinear speedup is caused by another effect which bene?ts our
parallel method: improved I/O. When sequential pipesort is applied to a 10 dimensional
data set, the lattice is partitioned into pipes of length up to 10. In order to process a pipe of
length 10, pipesort needs to write to 10 open ?les at the same time. It appears that under
LINUX, the number of open ?les can have a considerable impact on performance. For
100,000 records, writing them to 4 ?les each took 8 seconds on our system. Writing them
to 6 ?les each took 23 seconds, not 12, and writing them to 8 ?les each took 48 seconds,
not 16. This bene?ts our parallel method, since we partition the lattice ?rst and then apply
pipesort to each part. Therefore, the pipes generated in the parallel method are considerably
shorter.
In order to verify that our results also hold for newer machines with faster processors,
more memory per processor, and higher bandwidth, we ported our code to a SunFire 6800
and performed comparison tests on the same data sets. Figure 6 shows the running times
observed for the SunFire 6800. The absolute running times observed are considerably
faster, as expected. The SunFire is approximately 4 times faster than the PC cluster. Most

Figure

6. SunFire 6800 running time in seconds as a function of the number of processors. Same data set as in
?gure 5.
importantly, the shapes of the curves are essentially the same as for the PC cluster. The
runtime (slowest proc.) and average time curves are very similar and are both very close
to the theoretical optimum curve. That is, for an oversampling ratio of 2, an optimal
speedup of p is also observed for the SunFire 6800. The larger SunFire installation also
allowed us to test our code for a larger number of processors. As shown in ?gure 6, we still
obtain optimal speedup p when using 16 processors on the same dataset.

Figure

7 shows the PC cluster running times of our top-down data cube parallelization as
we increase the data size from 100,000 to 1,000,000 rows. The main observation is that the
parallel runtime increases slightly more than linear with respect to the data size which is
consistent with the fact that sorting requires time O(n log n). Figure 7 shows that our parallel
top-down data cube construction method scales gracefully with respect to the data size.

Figure

8 shows the PC cluster running time as a function of the oversampling ratio s.
We observe that, for our test case, the parallel runtime (i.e. the time taken by the slowest
processor) is best for 3. This is due to the following tradeoff. Clearly, the workload
balance improves as s increases. However, as the total number of subtrees, s ? p, generated
in the tree partitioning algorithm increases, we need to perform more sorts for the root
nodes of these subtrees. The optimal tradeoff point for our test case is s = 3. It is important
to note that the oversampling ratio s is a tunable parameter. The best value for s depends
on a number of factors. What our experiments show is that 3issuf?cient for the load
balancing. However, as the data set grows in size, the time for the sorts of the root nodes
of the subtrees increases more than linear whereas the effect on the imbalance is linear. For
substantially larger data sets, e.g. 1G rows, we expect the optimal value for s to be 2.

Figure

9 shows the PC cluster running time of our top-down data cube parallelization as
we increase the dimension of the data set from 2 to 10. Note that, the number of group-bys
that must be computed grows exponentially with respect to the dimension of the data set. In
?gure 9, we observe that the parallel running time grows essentially linear with respect to
194 DEHNE ET AL.

Figure

7. PC cluster running time in seconds as a function of the data size. (Fixed parameters: Number of
7. Experiments per data point = 5).

Figure

8. PC cluster running time in seconds as a function of the oversampling ratio s. (Fixed parameters: Data
rows. Number of processors = 8. Dimensions = 7. Experiments per data point = 5).

Figure

9. PC cluster running time in seconds as a function of the number of dimensions. (Fixed parameters: Data
200,000 rows. Number of processors = 8. Experiments per data point = 5.) Note: Work grows exponentially
with respect to the number of dimensions.
the output size. We also tried our code on very high dimensional data where the size of the
output becomes extremely large. For example, we executed our parallel algorithm for a 15-
dimensional data set of 10,000 rows, and the resulting data cube was of size more than 1G.

Figure

shows the PC cluster running time of our top-down data cube parallelization as
we increase the cardinality in each dimension, that is the number of different possible data

Figure

10. PC cluster running time in seconds as a function of the cardinality, i.e. number of different possible data
values in each dimension. (Fixed parameters: Data size = 200,000 rows. Number of processors = 8. Dimensions =
196 DEHNE ET AL.

Figure

11. PC cluster running time in seconds as a function of the skew of the data values in each dimension,
based on ZIPF. (Fixed parameters: Data size = 200,000 rows. Number of processors = 8. Dimensions = 7.
Experiments per data point = 5).
values in each dimension. Recall that, top-down pipesort [1] is aimed at dense data cubes.
Our experiments were performed for 3 cardinality levels: 5, 10, and 100 possible values per
dimension. The results shown in ?gure 6 con?rm our expectation that the method performs
better for denser data.

Figure

11 shows the PC cluster running time of our top-down data cube parallelization for
data sets with skewed distribution. We used the standard ZIPF distribution in each dimension
with data reduction in top-down pipesort [1] increases with
skew, the total time observed is expected to decrease with skew which is exactly what
we observe in ?gure 11. Our main concern regarding our parallelization method was how
balanced the partitioning of the tree would be in the presence of skew. The main observation
in ?gure 11 is that the relative difference between runtime (slowest processor) and average
time does not increase as we increase the skew. This appears to indicate that our partitioning
method is robust in the presence of skew.
7. Comparison with previous results
In this Section we summarize previous results on parallel data cube computation and compare
them to the results presented in this paper.
In [13, 14], the authors observe that a group-by computation is essentially a parallel pre?x
implementation of this method is mentioned and no experimental performance evaluation
is presented. This method creates large communication overhead and will most likely show
unsatisfactory speedup. The methods in [20, 22] as well as the methods presented in this
paper reduce communication overhead by partitioning the load and assigning sets of group-by
computations to individual processors. As discussed in [20, 22], balancing the load
assigned to different processors is a hard problem. The approach in [20] uses a simple
greedy heuristic to parallelize hash-based data cube computation. As observed in [20], this
simple method is not scalable. Load balance and speedup are not satisfactory for more
than 4 processors. A subsequent paper by the same group [31] focuses on the overlap
between multiple data cube computations in the sequential setting. The approach in [22]
considers the parallelization of sort-based data cube construction. It studies parallel bottom-up
Iceberg-cube computation. Four different methods are presented: RP, RPP, ASL, and
PT. Experimental results presented indicate that ASL, and PT have the better performance
among those four. The main reason is that RP and RPP show weak load balancing. PT is
somewhat similar to our parallel bottom-up data cube construction method presented in
Section 3 since PT also partitions the bottom-up tree. However, PT partitions the bottom-up
tree simply into subtrees with equal numbers of nodes, and it requires considerably more
tasks than processors to obtain good load balance. As observed in [22], when a larger
number of tasks is required, then performance problems arise because such an approach
reduces the possibility of sharing of pre?xes and sort orders between different group-by
computations. In contrast, our parallel bottom-up method in Section 3 assigns only two
tasks to each processor. These tasks are coarse grained which greatly improves sharing of
pre?xes and sort orders between different group-by computations. Therefore, we expect
that our method will not have a decrease in performance for a larger number of processors
as observed in [22]. The ASL method uses a parallel top-down approach, using a skiplist
to maintain the cells in each group-by. ASL is parallelized by making the construction
of each group-by a separate task, hoping that a large number of tasks will create a good
overall load balancing. It uses a simple greedy approach for assigning tasks to processors
that is similar to [20]. Again, as observed in [22], the large number of tasks brings with
it performance problems because it reduces the possibility of sharing of pre?xes and sort
orders between different group-by computations. In contrast, our parallel top-down method
in Section 4 creates only very few coarse tasks. More precisely, our algorithm assigns s
tasks (subtrees) to each processor, where s is the oversampling ratio. As shown in Section 6,
an oversampling ratio s ? 3issuf?cient to obtain good load balancing. In that sense, our
method answers the open question in [22] on how to obtain good load balancing without
creating so many tasks. This is also clearly re?ected in the experimental performance of
our methods in comparison to the experiments reported in [22]. As observed in [22], their
experiments (?gure 10 in [22]) indicate that ASL obtains essentially zero speedup when
the number of processors is increased from 8 to 16. In contrast, our experiments (?gure 6
of Section show that our parallel top-down method from Section 4 still doubles its speed
when the number of processors is increased from 8 to 16 and obtains optimal speedup p
when using processors.
8. Conclusion and future work
We presented two different, partitioning based, data cube parallelizations for standard shared
disk type parallel machines. Our partitioning strategies for bottom-up and top-down data
198 DEHNE ET AL.
cube parallelization balance the loads assigned to the individual processors, where the loads
are measured as de?ned by the original proponents of the respective sequential methods.
Subcube computations are carried out using existing sequential data cube algorithms. Our
top-down partitioning strategy can also be easily extended to parallelize the ArrayCube
method. Experimental results indicate that our partitioning methods are ef?cient in practice.
Compared to existing parallel data cube methods, our parallelization approach brings a
signi?cant reduction in inter-processor communication and has the important practical
bene?t of enabling the re-use of existing sequential data cube code.
A possible extension of our data cube parallelization methods is to consider a shared
nothing parallel machine model. If it is possible to store a duplicate of the input data set R
oneachprocessor'sdisk,thenourmethodcanbeeasilyadaptedforsuchanarchitecture.This
is clearly not always possible. It does solve most of those cases where the total output size is
considerably larger than the input data set; for example sparse data cube computations. The
data cube can be several hundred times as large as R. Suf?cient total disk space is necessary
to store the output (as one single copy distributed over the different disks) and a p times
duplication of R may be smaller than the output. Our data cube parallelization method would
then partition the problem in the same way as described in Sections 3 and 4, and subcube
computations would be assigned to processors in the same way as well. When computing
its subcube, each processor would read R from its local disk. For the output, there are two
alternatives. Each processor could simply write the subcubes generated to its local disk.
This could, however, create a bottleneck if there is, for example, a visualization application
following the data cube construction which needs to read a single group-by. In such a case,
each group-by should be distributed over all disks, for example in striped format. To obtain
such a data distribution, all processors would not write their subcubes directly to their local
disks but buffer their output. Whenever the buffers are full, they would be permuted over
the network. In summary we observe that, while our approach is aimed at shared disk
parallel machines, its applicability to shared nothing parallel machines depends mainly on
the distribution and availability of the input data set R. An interesting open problem is to
identify the ?ideal? distribution of input R among the p processors when a ?xed amount of
replication of the input data is allowed (i.e., R can be copied r times, 1 ? r < p).
Another interesting question for future work is the relationship between top-down and
bottom-up data cube computation in the parallel setting. These are two conceptually very
different methods. The existing literature suggests that bottom-up methods are better suited
for high dimensional data. So far, we have implemented our parallel top-down data cube
method which took about one person year of full time work. We chose to implement
the top-down method because it has more tunable parameters to be discovered through
experimentation. A possible future project could be to implement our parallel bottom-up
data cube method in a similar environment (same compiler, message passing library,
data structure libraries, disk access methods, etc.) and measure the various trade-off points
between the two methods. As indicated in [22], the critical parameters for parallel bottom-up
data cube computation are similar: good load balance and a small number of coarse
tasks. This leads us to believe that our parallel bottom-up method should perform well.
Compared to our parallel top-down method, our parallel bottom-up method has fewer
parameters available for ?ne-tuning the code. Therefore, the trade-off points in the parallel
setting between top-down and bottom-up methods may be different from the sequential
setting.
Relatively little work has been done on the more dif?cult problem of generating partial
data cubes, that is, not the entire data cube but only a given subset of group-bys. Given a
lattice and a set of selected group-bys that are to be generated, the challenge is in deciding
which other group-bys should be computed in order to minimize the total cost of computing
the partial data cube. In many cases computing intermediate group-bys that are not in the
selected set, but from which several views in the selected set can be computed cheaply, will
reduce the overall computation time. Sarawagi et al. [25] suggest an approach based on
augmenting the lattice with additional vertices (to represent all possible orderings of each
view's attributes) and additional edges (to represent all relationships between views). Then
a Minimum Steiner Tree approximation algorithm is run to identify some number of ?inter-
mediate? nodes (so-called Steiner points) that can be added to the selected subset to ?best?
reduce the overall cost. An approximation algorithm is used because the optimal Minimum
Steiner Tree problem is NP-Complete. The intermediate nodes introduced by this method
are,ofcourse,tobedrawnfromthenon-selectednodesintheoriginallattice.Byaddingthese
additional nodes, the cost of computing the selected nodes is reduced. Although theoretically
neat this approach is not effective in practice. The problem is that the augmented lattice
has far too many vertices and edges to be processed ef?ciently. For example, in a 6 dimensional
partial data cube the number of vertices and edges in the augmented lattice increase
by factors of 30 and 8684 respectively. For a 8 dimensional partial data cube the number
of vertices and edges increase by factors of 428 and 701,346 respectively. The augmented
lattice for a 9 dimensional partial data cube has more than 2,000,000,000 edges. Another
approach is clearly necessary. The authors are currently implementing new algorithms for
generating partial data cubes. We consider this an important area of future research.

Acknowledgments

TheauthorswouldliketothankStevenBlimkie,ZimminChen,KhoiManhNguyen,Thomas
Pehle, and Suganthan Sivagnanasundaram for their contributions towards the implementation
described in Section 6. The ?rst, second, and fourth author's research was partially
supported by the Natural Sciences and Engineering Research Council of Canada. The third
author's research was partially supported by the National Science Foundation under Grant
9988339-CCR.


--R













Introduction to Parallel Computing

Max Planck Institute











--TR
Probabilistic counting algorithms for data base applications
Optimal algorithms for tree partitioning
Introduction to parallel computing
Scalable parallel geometric algorithms for coarse grained multicomputers
Implementing data cubes efficiently
Towards efficiency and portability
An array-based algorithm for simultaneous multidimensional aggregates
Efficient external memory algorithms by simulating coarse-grained parallel algorithms
External memory algorithms
Bottom-up computation of sparse and Iceberg CUBE
Parallel virtual memory
A Shifting Algorithm for Min-Max Tree Partitioning
Iceberg-cube computation with PC clusters
Data Cube
High Performance OLAP and Data Mining on Parallel Computers
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms
Fast Computation of Sparse Datacubes
Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies
On the Computation of Multidimensional Aggregates
Multi-Cube Computation
BSP-Like External-Memory Computation
Bulk synchronous parallel computing-a paradigm for transportable software
A Parallel Scalable Infrastructure for OLAP and Data Mining

--CTR
Ying Chen , Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, Parallel ROLAP Data Cube Construction on Shared-Nothing Multiprocessors, Distributed and Parallel Databases, v.15 n.3, p.219-236, May 2004
Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, The cgmCUBE project: Optimizing parallel data cube generation for ROLAP, Distributed and Parallel Databases, v.19 n.1, p.29-62, January   2006
Ge Yang , Ruoming Jin , Gagan Agrawal, Implementing data cube construction using a cluster middleware: algorithms, implementation experience, and performance evaluation, Future Generation Computer Systems, v.19 n.4, p.533-550, May
Ying Chen , Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, PnP: sequential, external memory, and parallel iceberg cube computation, Distributed and Parallel Databases, v.23 n.2, p.99-126, April     2008
OLAP;partitioning;load balancing;parallel processing;data cube