Effect of Data Distribution in Parallel Mining of Associations.
Association rule mining is an important new problem in data mining. It has crucial applications in decision support and marketing strategy. We proposed an efficient parallel algorithm for mining association rules on a distributed share-nothing parallel system. Its efficiency is attributed to the incorporation of two powerful candidate set pruning techniques. The two techniques, distributed and global prunings, are sensitive to two data distribution characteristics: data skewness and workload balance. The prunings are very effective when both the skewness and balance are high. We have implemented FPM on an IBM SP2 parallel system. The performance studies show that FPM outperforms CD consistently, which is a parallel version of the representative Apriori algorithm (Agrawal and Srikant, 1994). Also, the results have validated our observation on the effectiveness of the two pruning techniques with respect to the data distribution characteristics. Furthermore, it shows that FPM has nice scalability and parallelism, which can be tuned for different business applications.
Introduction
Association rule discovery has attracted a lot of attention from the research and business communities [1, 2, 4].
An association rule is a rule which implies certain association relationships among a set of objects (such as "occur
together" or "one implies the other") in a database. The intuitive meaning of an association
Y are set of items, is that transactions of the database which contain X tend to contain Y . A classical example is
that 98% of customers that purchase tires and automobile accessories in a department store also have automotive
services carried out. This example is a typical association in a basket database which sounds like common sense
knowledge; however, there could be a lot of associations among the data which may not be able to deduce from
common knowledge. Therefore, efficient automated technique to discover this type of rules is a very important area
of research in data mining [2, 7, 8, 15, 17]. Applications of association rule mining range from decision support to
product marketing and consumer behavior prediction.
Previous studies examined efficient mining of association rules from many different angles. An influential association
rule mining algorithm, Apriori [2], has been developed for rule mining in large transaction databases. The
scope of the study has also been extended to efficient mining of sequential patterns [20], generalized association rules
[19], multiple-level association rules [9], quantitative association rules [21], constrainted association rules [14] etc.
Although these studies are on sequential data mining techniques, algorithms for parallel mining of association rules
have also been proposed [3, 16, 22, 23].
The development of parallel systems for mining of association rules has its unique importance - databases or
data warehouses [18] have been used more often to store a huge amount of data; data mining in such databases
require substantial processing power, and parallel system is a possible solution. This observation motivates us to
study efficient parallel algorithms for mining association rules in large databases. In this work, we study the problem
on parallel system with distributed share-nothing memory such as the IBM SP2 [11]. In this model, the database
is partitioned and distributed across the local disks of the processors; and the processors communicate via a fast
network.
It has been well studied that the major cost of mining association rules is the computation of the set of large
itemsets (i.e., frequently occurring sets of items, see Section 2.1) in the database [1, 2]. An itemset (a set of items)
is large if the percentage of transactions that containing all these items is greater than a given threshold. The most
representative parallel algorithm for mining association rules is the CD algorithm (Count Distribution), which is
designed for share-nothing parallel systems [3]. It extends directly the basic technique of Aprori to parallel system.
Our proposed algorithm, FPM (Fast Parallel Mining), has the following distinct feature in comparison with CD :
FPM has explored an important property between locally large itemsets (those that are large with respect to the
partition of a processor) and globally large itemsets (those that are large with respect to the entire database) to
develop two powerful pruning techniques, distributed pruning and global pruning, which can reduce the number of
candidate sets at each individual processor. Since the number of candidate sets is a dominant parameter of the
computation cost, with a substantially smaller candidate sets, FPM performs much better than CD.
Another contribution of this work is the discovery that the effectiveness of the two aforementioned pruning
techniques, and hence the performance of the parallel mining, depends on the data distribution characteristics in the
database partitioning. We have captured the distribution characteristics in two factors : data skewness and workload
balance. These two factors are orthogonal properties. Intuitively, a partitioned database has high data skewness if
most globally large itemsets are locally large only at a very few partitions. On the other hand, a partitioned database
has a high workload balance if all the processors have similar number of locally large itemsets in their partitions.
(More precise definitions of skewness and workload balance will be given in Sections 3 & 4.) We have defined metrics
to measure data skewness and workload balance. We found out that both the distributed and global prunings have
super performance in the best case of high data skewness and high workload balance. The combination of high
balance with moderate skewness is the second best case. On the other hand, the high skewness, moderate balance
combination only provide moderate improvement over CD, while the combination of low skewness and low balance
is the worst case in which only marginal improvement can be found.
We have implemented FPM on an IBM SP2 parallel machine with processors. Extensive performance studies
have been carried out. The results confirm our observation on the relationship between pruning effectiveness and
data distribution.
The rest of this paper is organized as follows. Section 2 overviews the parallel mining of association rules. The
techniques of distributed and global prunings, together with the FPM algorithm are described in Section 3. In the
same section, we have also investigated the relationship between the effectiveness of the prunings and the two data
distribution characteristics of data skewness and workload balance. In section 4, we define metrics to measure data
skewness and workload balance of a data partition. Section 5 reports the result of an extensive performance study.
In Section 6, we discuss a few issues including possible extensions of FPM to enhance its scalability. Section 7 is the
conclusion.
2 Parallel Mining of Association Rules
2.1 Sequential Algorithm for Mining Association Rules
be a set of items. Let D be a database of transactions, where each transaction T consists
of a set of items such that T ' I . Given an itemset X ' I , a transaction T contains X if and only if X ' T . An
association rule is an implication of the form X [2]. The association rule
holds in D with confidence c if the probability of a transaction in D which contains X also contains Y is c.
The association rule X ) Y has support s in D if the probability of a transaction in D contains both X and Y is
s. The task of mining association rules is to find all the association rules whose support is larger than a minimum
support threshold and whose confidence is larger than a minimum confidence threshold.
For an itemset X , its support is the percentage of transactions in D which contains X , and its support count,
denoted by X :sup , is the number of transactions in D containing X . An itemset X is large (or more precisely,
frequently occurring) if its support is no less than the minimum support threshold. An itemset of size k is called a
k-itemset. It has been shown that the problem of mining association rules can be reduced to two subproblems [1]:
(1) find all large itemsets for a given minimum support threshold, and (2) generate the association rules from the
large itemsets found. Since (1) dominates the overall cost of mining association rules, the research has been focused
on developing efficient methods to solve the first subproblem [2].
An interesting serial algorithm, Apriori [2], has been proposed for computing large itemsets at mining association
rules in a transaction database, which is outlined as follows [2].
The large itemsets are computed through iterations. At each iteration, Apriori scans the database once and
finds all the large itemsets of the same size. At the k-th iteration, Apriori creates the set of candidate sets C (k)
by applying the candidate set generating function Apriori gen on L (k\Gamma1) , where L (k\Gamma1) is the set of all large
1)-itemsets found at the (k \Gamma 1)-st iteration, and Apriori gen generates only those k-itemset candidates
whose every 1)-itemset subset is in L (k\Gamma1) .
2.2 Count Distribution Algorithm for Parallel Mining
CD (Count Distribution) is a parallel version of Apriori. It is one of the earliest proposed and representative parallel
algorithms for mining of association rules [3]. We describe here briefly its steps for comparison purpose. The database
D is partitioned into distributed across n processors. The program fragment of CD at processor
k-th iteration is outlined in Figure 1. (For convenience, we use X :sup(i) to represent the local
support count of an itemset X in partition D i .) In step 1, every processor computes the same candidate set C k by
applying the aprior gen function on L k\Gamma1 , which is the set of large itemsets found at the (k \Gamma 1)-th iteration. In
step 2, local support counts (support in D i ) of candidates in C k are found. In steps 3 & 4, local support counts are
exchanged with all other processors to get global support counts (support in D) and globally large itemsets (large
with respect to D) L k are computed independently by each processor. CD repeats steps 1 - 4 until no more candidate
is found. We have implemented CD on an IBM SP2 using the MPI (Message Passing Interface) [13].
scan partition D i to find the local support count X :sup(i) for all
with all other processors to get global support counts X :sup , for all

Figure

1: Count Distribution Algorithm
Pruning Techniques and the FPM Algorithm
3.1 Distributed Pruning
It is important to observe some interesting properties related to large itemsets in a parallel environments since such
properties may substantially reduce the number of candidate sets. (The preliminary form of the results in this section
have been developed in [6] and extended here.) First, there is an important relationship between large itemsets and
the processors in the database: every globally large itemsets must be locally large at some processor(s). If an itemset
X is both globally large and locally large at a processor p i , X is called gl-large at processor p i . The set of gl-large
itemsets at a processor will form a basis for the processor to generate its own candidate sets.
Second, a gl-large itemset at a processor has the following monotonic subset relationship property: if an itemset
is gl-large at a processor p i , all of its subsets are also gl-large at p i . Combining these two properties, we have the
following results.
Lemma 1 If an itemset X is globally large, there exists a processor n), such that X and all its subsets
are gl-large at processor p i . 1
We use GL i to denote the set of gl-large itemsets at processor p i , and GL i(k) to denote the set of gl-large k-itemsets
at processor p i . It follows from Lemma 1 that if X 2 L (k) , then there exists a processor p i , such that all its
are gl-large at processor p i , i.e., they belong to GL i(k\Gamma1) .
In a straightforward adaptation of Apriori, the set of candidate sets at the k-th iteration, denoted by CA (k) ,
which stands for size-k candidate sets from Apriori, would be generated by applying the Apriori gen function on
L (k\Gamma1) . That is,
At each processor p i , let CG i(k) be the set of candidates sets generated by applying Apriori gen on GL i(k\Gamma1) , i.e.,
where CG stands for candidate sets generated from gl-large itemsets. Hence CG i(k) is generated from GL i(k\Gamma1) .
Since GL i(k\Gamma1) ' L (k\Gamma1) , CG i(k) is a subset of CA (k) . In the following, we use CG (k) to denote the set [ n
Theorem 1 For every k ? 1, the set of all large k-itemsets L (k) is a subset of CG
This result is stronger than that in [17] - the result there states that a globally large itemset is locally large in some partition; while
states that all its subsets must be locally large together at the same partition.
Proof. Let It follows from Lemma 1 that there exists a processor n), such that all the
subsets of X are gl-large at processor p i . Hence X 2 CG i(k) . Therefore,
indicates that CG (k) , which is a subset of CA (k) and could be much smaller than CA (k) , can be taken
as the set of candidate sets for the size-k large itemsets. In effect, the set of candidates in CA (k) has been pruned
down to those in CG (k) - we called this technique distributed pruning. This result forms a basis for the reduction of
the set of candidate sets in the algorithm FPM. First the set of candidate sets CG i(k) can be generated locally at each
processor p i at the k-th iteration. After the exchange of support counts, the gl-large itemsets GL i(k) in CG i(k) can
be found at the end of that iteration. Based on GL i(k) , the candidate sets at processor p i for the 1)-st iteration
can then be generated according to Theorem 1. According to our performance studies, the number of candidate sets
generated by distributed pruning can be substantially reduced to about of that generated in CD.
Example 1 illustrates the effectiveness of the reduction of candidate sets using distributed pruning.
Example 1 Assuming there are 3 processors in a parallel system in which the database D has been partitioned into
Suppose the set of large 1-itemsets (computed at the first iteration) L G; Hg,
in which A; B, and C are locally large at processor p 1 , B; C, and D are locally large at processor p 2 , and E; F; G, and
H are locally large at processor p 3 . Therefore, GL G; Hg.
Based on Theorem 1, the set of size-2 candidate sets at processor p 1 is CG
fAB;BC;ACg. Similarly, CG EG;EH;FG;FH;GHg. Hence, the set
of candidate sets for large 2-itemsets is CG candidates.
However, if Apriori gen is applied to L (1) , the set of candidate sets CA would have 28
candidates. This shows that it is very effective to apply distributed pruning to reduce the candidate sets. 2
3.2 Global Pruning
As a result of the count exchange, the local support counts X :sup(i) , for all processor are also
available at every processor. With this information, another powerful pruning technique called global pruning can
be developed. Let X be a candidate k-itemset. At each partition D i , X :sup(i) - Y :sup(i) , if Y ae X . Therefore the
local support count of X , X :sup(i) , is bounded by the value minfY 1g. Since the global
support count of X , X :sup , is the sum of its local support count at all the processors, the value
is an upper bound of X :sup . If X :maxsup ! minsup \Theta jDj, then X can be pruned away. This technique is called global
pruning. Note that global pruning requires no additional information except the local support counts resulted from
count exchange in the previous iteration.

Table

1 gives an example to show that global pruning can pruning away candidates which cannot be pruned by
distributed pruning. Suppose the global support count threshold is 15 and the local support count threshold at each
local support at processor 1 13
local support at processor 2 3 3 12 34 1 4
local support at processor 3
global support
gl-large at processor 1
\Theta \Theta
gl-large at processor 2 \Theta \Theta
gl-large at processor 3 \Theta \Theta \Theta \Theta

Table

1: High data skewness and high workload balance case
processor is 5. Distributed pruning cannot prune away CD, as C and D are both gl-large at processor 2. Whereas
global pruning can prune away CD, as CD
can also be pruned, because EF would survive global
pruning. From this example, it is clear that global pruning is more effective than distributed pruning, i.e., what can
pruned away by distributed pruning will be pruned away by global pruning. The three pruning techniques, the one
in apriori gen, the distributed and global prunings, have increasing pruning power, and the latter ones subsume the
previous one.
3.3 Fast Parallel Mining Algorithm (FPM)
We present the FPM algorithm in this section. It is an enhancement of CD. The simple support counts exchange
scheme in CD is retained in FPM. The main difference is the incorporation of both the distributed and global
prunings in FPM to reduce the candidate set size.
The first iteration of FPM is the same as CD. Each processor scans its partition to find out local support counts
of all size-1 itemsets and use one round of count exchange to compute the global support counts. At the end of the
1-st iteration, in addition to L 1 , each processor also finds out the gl-large itemsets GL 1(i) , for
For the k-th iteration of FPM, k ? 1, the program fragment executed at processor i, 1 - i - n, is described in

Figure

2.
compute candidate sets CG
(distributed pruning)
prune candidates in CG k by global pruning;
scan partition D i to find the local support count X :sup(i) for all remaining candidates
with all other processors to get global support counts X :sup , for all
return

Figure

2: The FPM Algorithm
Similar to CD, FPM is also implemented by collective communication operations of MPI on the SP2.
In order to compare the effects of distributed and global pruning, we have also implemented a variant FNG (FPM
with no global pruning) of FPM. FNG does not perform the global pruning, i.e., it's procedure is the same as that
in

Figure

2, except step 2 is removed.
4 Data Skewness and Workload Balance
In a database partition, two data distribution characteristics, data skewness and workload balance, have orthogonal
effects on prunings and hence performance of FPM.
Intuitively, the data skewness of a partitioned database is high if the supports of most large itemsets are clustered
in a few partitions. It is low if the supports of most large itemsets are distributed evenly across the processors. In

Table

1, it is clear that all the itemsets have high skewness.
For a partition with high skewness, even though the support of each large itemset is clustered at a few processors,
the clusterings of different large itemsets may be distributed evenly across the processors or concentrated on a few of
them. In the first case, the clusterings of the large itemsets are distributed evenly among the processors; hence, each
processor would have similar number of locally large itemsets. We characterise this case as high workload balance. In
the second case, the clusterings would be concentrated on a few processors; hence some processors would have much
more locally large itemsets than the others. This is the low workload balance case. For example, the itemsets in

Table

1 not only have high skewness, it also has a good workload balance; because A, B are locally large at processor
1, and C, D at processor 2, whereas E, F at processor 3.
It follows from our discussion of the pruning techniques that high data skewness would increase the chance of
candidate sets pruning; however, it is not the only factor, workload is another critical factor. In the following, we will
see that given a good data skewness, if the distribution of the clusterings amount the processors are not even, then
the pruning effects would be reduced significantly, and, to aggravate the problem more, the work of computing the
large itemsets would be concentrated on a few processors which is a very troublesome issue for parallel computation.
Example 2 As explained above, Table 1 is a case of high data skewness and high workload balance. The supports of
each itemset are distributed mostly in one partition; hence, the skewness is high. On the other hand, every partition
has the same number of locally large itemsets; therefore, the workload balance is also high. In this case, CD will
generate
candidates in the second iteration. Whereas, the distributed pruning will generate only three
candidates AB, CD and EF , which shows that the pruning has good effect for this distribution.
local support at processor 1 13 33 12 34 2 1
local support at processor 2
local support at processor 3
global support
gl-large at processor 1
gl-large at processor 2 \Theta \Theta \Theta \Theta \Theta \Theta
gl-large at processor 3 \Theta \Theta \Theta \Theta

Table

2: High data skewness and low workload balance case

Table

2 is an example of high data skewness but low workload balance. The thresholds are the same as that in

Table

1, i.e., the global support threshold is 15 and the local support threshold at each processor is 5. The support
count distribution of each item is the same as that in Table 1 except that items A; B; C and D are now locally
large together at processor 1 instead of distributed between processors 1 and 2. In this lower workload balance case,
distributed pruning will generate 7 size-2 candidates, namely AB, AC, AD, BC, BD, CD and EF , while CD will
still have 15 candidates. Thus, the distributed pruning remains to be very effective, but not as good as that in the
high workload balance case (Table 1).
local support at processor 1 6 12 4 13 5 12
local support at processor 2 6 12 5 12 4 13
local support at processor 3
global support
gl-large at processor 1
\Theta
gl-large at processor 2
\Theta
gl-large at processor 3 \Theta

Table

3: Low data skewness and high workload balance case

Table

3 is an example of low data skewness and high workload balance. The support counts of the items A,
B, C, D, E and F are almost equally distributed over the 3 processors. Hence, the data skewness is low. On the
other hand, the workload balance is high, because the number of locally large itemsets in each processor is almost
the same. In this case, both CD and distributed pruning generate the same 15 candidate sets; hence, if we restrict
pruning to the distributed pruning, then it has no advantage over CD in this case. However, global pruning can
prune away the candidates AC, AE and CE. In other words, FPM still has a 20% of improvement over CD in this
pathological case of low skewness and high balance. 2
Following Example 2, it is observed that global pruning is more effective than distributed pruning and can perform
significant candidates reduction even in the moderate data skewness or low workload balance cases. As a note, low
skewness and low balance cannot occur together. Also, according to our analysis, distributed pruning can prune away
almost
n (n is the number of partitions) of all the size-2 candidates generated by CD in the high data skewness
and high workload balance case.
In summary, distributed pruning is very effective when a database is partitioned with high skewness and high
balance. On the other hand, in the worst cases of high skewness with low balance or high balance with low skewness,
the effect of distributed pruning is degraded to the level in CD, however, global pruning may still perform better than
CD. To strengthen our studies, we investigated the problem of defining metrics to measure skewness and balance.
4.1 Data Skewness Metric
We have developed a skewness metric based on the well established notion of entropy [5]. Given a random variable
entropy is a measurement on how even or uneven its probability distribution is over its values. If a database
is partitioned over n processors, the value pX
X:sup can be regarded as the probability of occurrence of an
itemset X in partition D i , n). The entropy
log(p X (i))) is a measurement of the
distribution of the local supports of X over the partitions. For example, if X is skewed completely into a single
partition D k , (1 - k - n), i.e., it only occurs in D k , then pX k. The value of
is the minimal in this case. On the other hand, if X is evenly distributed among all the partitions, then pX
the value of log(n) is the maximal in this case. Therefore the following metric can be used
to measure the skewness of a data partition.

Table

local count at processor 1 13
local count at processor 2 1 3 12 34 1 4 0.348
high local count at processor 3
data skewness S(X) 0.452 0.633 0.429 0.697 0.429 0.586
high TS(D) 0.494
workload balance TB(D) 0.999

Table

local count at processor 1 13 33 12 34 2 1 0.601
local count at processor 2
high local count at processor 3
data skewness S(X) 0.452 0.633 0.429 0.697 0.429 0.586
low TS(D) 0.494
workload balance TB(D) 0.789

Table

3 local count at processor 1 6 12 4 13 5 12 0.329
local count at processor 2 6 12 5 12 4 13 0.329
low local count at processor 3
data skewness S(X) 0.015 0.001 0.012 0.001 0.012 0.001
high TS(D) 0.005
workload balance TB(D) 0.999

Table

4: Data Skewness and Workload Balance
Given a database partition D i , (1 - i - n), the skewness S(X) of an itemset is defined by
log(n).
The skewness S(X) has the following properties:
the skewness is at its lowest value when X is distributed
evenly in all partitions.
such that pX the skewness is at its
highest value when X occurs only in one partition.
in all the other cases.
It follows from the property of entropy that S(X) increases with respect to the skewness of X ; hence, it is a
suitable metric for the skewness of an individual itemset. Table 4 shows the skewness of the large itemsets in Tables 1,
2 and 3.
In addition to measuring the skewness of an itemset, we also need a metric to measure the skewness of the
database partition. We define the skewness of a database partition as a weighted sum of the skewness of all the large
itemsets. In other words, the skewness of a partition is a measurement of the total skewness of all the large itemsets.
Given a database partition D i , (1 - i - n), the skewness TS(D) of the partition is defined by
X2LS S(X) \Theta w(X), where LS is the set of all the large itemsets,
Y 2I S
Y:sup
is the weight of
the support of X over all the large itemsets in LS , and S(X) is the skewness of X.
TS(D) has some properties similar to S(X).
when the skewness of all the itemsets are at its minimal value.
when the skewness of all the itemsets are at its maximal value.
in all the other cases.
In

Table

4, the skewness TS(D) of the partitions for the three situations have computed. (For illustration purpose,
we only have computed TS(D) with respect to the skewness of all the size-1 large itemsets.) Note that we have
ignored the small itemsets in the computation of the skewness of a partition. Since the purpose of our task is to
investigate the effect of data skewness on candidate sets pruning, and this only involves large itemsets, this restriction
would in fact make the metric more relevant to candidate set pruning.
4.2 Workload Balance Metric
Workload balance is a measurement of the distribution of the support clusterings of the large itemsets over the
partitions at the processors. Based on the definition of w(X) in Definition 2 and that of pX (i) in Definition 1, we
define
X2Ls w(X) \Theta pX (i) to be the itemset workload in a partition D i , where L s is the set of all the large
itemsets. Intuitively, the workload W i in partition D i is the ratio of the total supports of the large itemsets in D i
over all the partitions. Note that
A partition has high workload balance if W i are the same for all partitions D i , On the other hand,
if distribution of W i over the partitions are very uneven, then the workload balance is low. As has been pointed
out, the workload balance has important bearing on the pruning and performance of parallel mining. In parallel to
the metric for data skewness, we also define a metric workload balance factor to measure the workload balance of a
partition, which is based also on entropy.
Definition 3 For a database partition D i , database D, the workload balance factor TB(D) of the
partition is given by
log(n) .
The metric TB(D) has the following properties:
when the workload across all processors are the same;
when the workload is concentrated on one processor;
in all the other cases.
In

Table

4, the workload W i of the first and last cases (Tables 1 and 3) have a high balance, and the values of
are almost equal to 1. In the second case (Table 2), the workload at processor 2 has been shifted to processor
1, and hence created an unbalance case; the value of TB(D) thus has been reduced to 0.789, which indicates a
moderate workload balance.
The data skewness metric and workload balance factor are not independent. Theoretically, each one of them
could have values range from 0 and 1. However, some combinations of their values are not admissable. First, let us
consider some boundary cases.
Theorem 2 Let be a partition of a database D.
1. If then the admissable values of TB(D) range from 0 to 1. If
2. If then the admissable values of TS(D) range from 0 to 1. If
Proof:
1. By definition 0 - TB(D) - 1. What we need to prove is that the boundary cases are admissable when
implies that large itemsets X. Therefore, each large itemset is large
at one and only one processor. If all the large itemsets are large at the same processor i, (1 - i - n), then
On the other hand, if each processor
has the same number of large itemsets, then W
then large itemsets X . This implies that W i are the same for all 1 - i - n. Hence
2. It follows from the first result of this theorem that both are admissable when
1. Therefore the first part is proved. Furthermore, if there exists a partition D i ,
This implies that all large itemsets are locally
large at only D i . Hence shown in Theorem 2 that not all possible combinations
are admissable. In general, the admissable combinations will be a subset of the unit square such as the one in Figure 3.
It always contains the two segments Figure 3) and Figure 3), but not the
After defining the metrics and studying their characteristics, we can validate our observation
on the relationship between data skewness, workload balance and candidates pruning effect in our performance
studies.
Performance Studies
In order to confirm our analysis that the proposed FPM is an efficient algorithm for mining associations in a parallel
system, we have implemented all the algorithms on an IBM SP2 and carried out a substantial performance evaluation
and comparison.
We have the following three goals in our studies: (1) to verify that FPM is faster than the representative algorithm
CD, and confirm that the major performance gain is from the two pruning techniques; (2) to confirm the observation
that both data skewness and workload balance are two critical factors in the performance of FPM; (3) to demonstrate
that FPM has good parallelism and scalability as a parallel algorithm.
We implemented FPM, its variant FNG, and CD. The IBM SP2 parallel system we used has
processors (66.7MHz) with 64 MB main memory, running the AIX operating system. Communication between

Figure

3: Admissable Combinations of Skewness(S) and Balance(B)
processors are through a high performance switch with an aggregated peak bandwidth of 40 MBps and a latency of
about 40 microseconds. Data was allocated to the local disk in each processor, and the database partition on each
node is about 100MB in size.
In order to be able to control the experiments to test different data distributions and scenarios, many works
[2, 3, 9, 15, 16] in mining association rules have adopted the standard technique introduced in [2] to generate the
database. We have enhanced the technique for the generation of database partitions and introduced parameters to
control the skewness and workload balance. Table 5 is a list of the parameters used in our synthetic databases.
Details of the data generation technique is in the appendix.
D number of transactions in each partition
average size of the transactions
I average size of the maximal potentially large itemsets
L number of maximal potentially large itemsets
N number of items
partition skewness
n number of partitions

Table

5: Synthetic Database Parameters
5.1 Relative Performance
In order to compare the performance between FMP, FNG, and CD, a databases and twenty data sets have been
generated. The data sets generated and their skewness and balance factors are listed in Table 6. The number of
partitions in each case is and the size of each partition is about 100MB. The name of a partition is
denoted by Dx.Ty.Iz.Sr.Bl, where x is the number of transactions in each partitions, y is the average size of the
transactions, z is the average size of the itemsets. The two parameters Sr and Bl are two important parameters
used to control the skewness and workload balance in the data generation. (The Bl values are listed separately in
the table.) In Table 6, we have also computed the measured skewness TS(D) and the balance factor TB(D) of the
partitions generated. It is important to note that these measured skewness and workload are very close to the values
of the controlled parameters, i.e., the values of S and B are good approximations of values of TS(D) and TB(D).
In addition, they cover a wide range of skewness and balanace. Thus, our synthesized data partitions are good
simulation of data partitions of various distribution characteristics. We believe this is technically valuable because
even real data may not be general enough to cover all possible distributions.
Name

Table

Attributes of Synthetic Databases
We ran FPM, FNG and CD on the database partitions in Table 6. The minimum support threshold is 0.5%. The
improvement of FPM and FNG over CD in response time are recorded in Table 7, and the result is very encouraging.
FPM and FNG are consistently faster than CD in all cases. In the following, we analyze the performance gain
of FPM and FNG in three aspects: (1) improvement when the workload balance is high, and the skewness varies
from high to moderate; (2) improvement when the skewness is high, and the workload balance varies from high to
moderate; (3) desirable and undesirable combinations of skewness and workload balance values.
Response Time FPM/CD FNG/CD

Table

7: Performance Improvement of FPM and FNG over CD

Figure

4 is the relative performance between FPM, FNG and CD on partitions with different skewness and a high
balance value performs much better than CD when the skewness is relatively high (s ? 0:5). On the
Response
time(sec.)
Relative Performance-D3278K.T5.I2.S?.B100(n=16, minsup=0.5%)
CD

Figure

4: Relative Performance on Databases with High Balance and Different Skewness
other hand, FPM outperforms CD significantly even when the skewness is in the moderate range, (0:1 - s - 0:5).
When B=90, the result in Table 7 shows that FPM is again much faster than CD. This demonstrates that FPM
outperforms CD consistently given a high workload balance and at least a moderate skewness.1000300050000 0.1 0.3 0.5 0.7 0.9 1
Response
time(sec.)
Relative Performance-D3278K.T5.I2.S90.B?(n=16, minsup=0.5%)
CD

Figure

5: Relative Performance on Databases with High Skewness and Different Workload Balance

Figure

5 is the relative performance given a high skewness different workload balance. Both FPM
and FNG perform much better than CD when the workload balance is relatively high (B ? 0:5); however, the
improvement in the range of moderate balance, (0:1 - B - 0:5), is marginal. This confirms our observation that
workload balance is an essential requirement. It shows that a high skewness has to accompany by a high workload
balance. The effect of a high skewness with a moderate balance may not be as good as that of a high balance with
a moderate skewness.
In

Figure

6, we vary both the skewness and balance together from a low value range to a high value range. The
Response
time(sec.)
Skewness and Balance(S,B)
Relative Performance-D3278K.T5.I2.S?.B?(n=16, minsup=0.5%)
CD

Figure

Relative Performance on Databases when both Skewness and Balance change
trend shows that the improvement of FPM over CD increases faster when both values approach the high value range.
Combining the observations in the above three cases together with the results in Table 7, we can divide the area
covering all the admissable combinations of skewness and balance in our experiments into four performance regions
as shown in Figure 7. Region A is the most favorable region in which the balance is high and the skewness varies
from high to moderate. FPM in general is 50% to 100% faster than CD. In region B, the workload balance value has
degraded moderately and the skewness remains high; in this case, the gain in FPM over CD is around 50%. Region
covers combinations that have very low workload balance; the gain in FPM falls into a moderate range of about
30%. Region D contains the most undesirable combinations; FPM only has marginal performance gain.

Figure

8 provides us another view to understand the candidates pruning effects. It shows the ratio on the number
of candidate sets between FPM (FNG) and CD for the same experiments in Figure 4. The reduction ratios for
the runs in the database D3278K.T5.I2.Sr.B100, are in the first graph. When the skewness
is high, distributed pruning has a 79.2% of reduction in candidate sets comparing with CD, and global
pruning has a 93.9% reduction. When the skewness is low, distributed pruning only has a 6.6% reduction,
but global pruning has a 30.7% reduction. This confirm our observation on the effect of high balance combined with
high or moderate skewness.
5.2 Scalability and Parallelism : Speedup and Scaleup
In order to study the efficiency of FPM as a parallel algorithm, we investigate its speedup and scaleup against CD.
Speedup is the reduction in response time vs the number of processors, given that the total size of the database
remains unchanged. The more processors are used, the faster the computation should be. The ideal speedup is
a linear function on the number of processors. Scaleup is the performance vs the number of processors when the
database size is scaled up proportional to the number of proccesors. If the algorithm has high efficiency and low
overhead, its performance would maintain uniform when both the number of processors and the size of the database
scaled up proportionally.
In the speedup experiment, we execute the algorithms on a fixed size database with various number of processors


* A

Figure

7: Performance regions (FPM/CD) in the admissible combinations of skewness and workload
on
number
of
candidate
sets
Pruning Effect-D3278K.T5.I2.S?.B100(n=16, minsup=0.5%)
Apriori_gen(no pruning)
Distributed Pruning/Apriori_gen
Global Pruning/Apriori_gen

Figure

8: Pruning Effect on Databases in Figure 4
Response
time(sec.)
Number of processors
CD
FPM14122028
Number of processors
Relative Speedup-D3278K.T5.I2.S90.B100
CD

Figure

9: Speedup on a Database
and partitions. We selected the database with high skewness and balance as a presentative to perform the study.
The database is listed in Table 8. It has a total size of 1.6GB, and was first divided into 16 partitions. Subsequently,
we combined the partitions to form databases with 8, 4, 2, and zero partitions.

Figures

9 is the execution times and speedups of FPM, FNG, and CD on the databases. The speedups are also
shown in Table 8. FNG had a linear speedup and FPM achieved a remarkable superlinear speedup. The reason
behind FPM's superlinear speedup is the increase in the skewness when the number of partitions increases.
In the scaleup experiment, both the database size and the number of processors are scaled up proportionally.
The number of processors involved were increased from 1 to 16, and the sizes of the databases were increased
correspondingly from 100MB to 1.6GB. Each database were partitioned according to the number of processors such
that every partition is maintained at the size of 100MB. We performed the experiment based on the database
D3278K.T5.I2.S90.B100, i.e., the databases are generated with the same parameters. Figure 10 shows the result of
the experiment. Surprisingly, both FPM and FNG not only can maintain the performance, their response time in
Databases Speedup of FPM Speedup of FNG Speedup of CD

Table

8: Speedup on five databases with different distribution characteristics
fact had gone down when the database was scaled up. The prime reason for this is the increase in pruing capability
when the number of partitions increases.
6 Discussion
To restrict the search of large itemsets in a small set of candidates is essential to the performance of mining association
rules. The pruning techniques we proposed are theoretically interesting, because they have effect only in the parallel
case but not the serial case. Both distributed and global pruning provide significant amount of pruning power, in
particular, when the data distribution is in a favorable situation, i.e. when workload balance is high and the skewness
is at least at a moderate level. It is important to study partition techniques that can deliver a good data distribution.
Random approaches in general will deliver partitions which have good balance. However, the skewness would be
difficult to guarantee together with good workload balance. Clustering technique such as the k-means algorithm [12]
will give good skewness. It remains an open problem how to modify clustering technique to generate partitions which
have good skewness and also good workload balance.
7 Conclusion
A parallel algorithm FPM for mining association rules has been proposed. A performance study carried out on
an IBM SP2 shared-nothing memory parallel system shows that FPM consistently outperforms CD. It also has
nice scalability in terms of speedup and scaleup. The gain in performance in FPM is due mainly to the pruning
techniques incorporated. It was discovered that the effectiveness of the pruning techniques depend highly on the
data distribution characteristics, which can be measured by two data skewness and workload balance. Our
analysis and experiment results show that the pruning techniques are very sensitive to workload balance, though
good skewness will also have important positive effect. The techniques are very effective in the best case of high
balance and high skewness. The combination of high balance and moderate skewness is the second best case. In the
worst case of low balance and low skewness, FPM can only deliver the performance close to that of CD. Since mining
associations has many interesting applications, important future works would include fine tuning of the proposed
parallel techniques on real business cases.



--R

Mining Association Rules between Sets of Items in Large Databases.
Fast algorithms for mining association rules.
Parallel mining of association rules: Design
Dynamic itemset counting and implication rules for market basket data.
Elements of information theory.
A fast distributed algorithm for mining association rules.
Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique.
Advances in Knowledge Discovery and Data Mining.
Discovery of Multiple-level association rules from large databases
Scalable parallel data mining for association rules.
Scalable POWERparallel Systems
Some methods for classification and analysis of multivariate observations
Message Passing Interface Forum.
Exploratory Mining and Pruning Optimizations of Constrainted Association Rules.
An effective hash-based algorithm for mining association rules
Efficient Parallel Data Mining for Association Rules.
An efficient algorithm for mining association rules in large databases.
Database Achievements and Opportunities Into the 21st Century.
Mining generalized association rules.
Mining sequential patterns: Generalizations and performance improvements.
Mining quantitative association rules in large relational tables.
Hash based parallel algorithms for mining association rules.
Parallel data mining for association rules on shared-memory multi-processors
--TR

--CTR
Frans Coenen , Paul Leng, Partitioning strategies for distributed association rule mining, The Knowledge Engineering Review, v.21 n.1, p.25-47, March 2006
Vipin Kumar , Mohammed Zaki, High performance data mining (tutorial PM-3), Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.309-425, August 20-23, 2000, Boston, Massachusetts, United States
data skewness;data mining;workload balance;parallel mining;association rules;parallel computing