Abstract
Abstract -In this paper we consider the problem of parallel mining of association rules on a sharedmemory multiprocessor system. Two efficient algorithms PSM and HSM have been proposed. PSM adopted two powerful candidate set pruning techniques distributed p r u n i n g and global p r u n i n g to reduce the size of candidates. HSM further utilized an 1 / 0 reduction strategy to enhance its performance. We have implemented PSM and HSM on a SGI Power Challenge parallel machine. The performance studies show that PSM and HSM out perform CD-SM, which is a shared-memory parallel version of the popular Apriori algorithm.
I. INTRODUCTION
Mining associiition rules in large databases has attracted a lot of attention in data mining research [l, 2, 4, 81. The mining process needs to scan all the transactions in the database, which introduces a significant amount of I/Os. In addition, it has to search through a large number of candidates for large itemsets which demands a lot of CPU computation. Therefore, the development of parallel algorithms for mining association rules is an important problem. In this work, we attempt to solve this problem on shared-memory multiple-processor machines such as the SGI Power Challenge.
I. INTRODUCTION
Most proposals in parallel mining have been focused on distributed or shared-nothing model [5, 6, 7, 9, lo] . In those models, the database is partitioned and distributed in the local disk of the processors. The memory limitation and I/O cost are the dominating performance factors. The shared-memory multiprocessor parallel machine is another important computing model. But very few parallel mining works have been carried out on this model. A direct extension of the Apriori algorithm to the shared-memory model has been presented in [ll] . Some important characteristics of the candidate sets in a partitioned database have been discovered [5] . They have been used to design two effective two pruning techniques, the distributed pruning and global pruning, which can reduce the amount of candidates effectively in the distributed or One of the first parallel algorithm in shared-nothing model is the CD (Count Distribution) algorithm [3] . For comparison purpose, we have realized the CD algorithm on a SGI Power Challenge shared-memory multiprocessor machine. This version of CD is called CD-SM (CD on Shared-memory Model).
I. INTRODUCTION
In this work, we propose two efficient algorithms on the shared-memory multi-processor machine. The first algorithm is PSM (Parallel mining on Shared-memory Model) which adopts the two pruning techniques to reduce the number of candidates in each iteration. PSM remedies the problem of large number of candidate sets in the CD-SM algorithm. So PSM consumes less computing time than the CD-SM. However, PSM still needs to perform the same number of scannings on the database. In general, the number of candidates after iteration two would reduce drastically. Therefore, we have reduced the number of scannings by combining the computations of all the iterations after iteration two. This enhanced version is the HSM (Hybrid parallel mining on Shared-memory Model) algorithm. Therefore, HSM can reduce the 1/0 cost at most situations (i.e., when need to mine more than two iterations in CD-SM), and has less CPU cost compared with CD-SM.
I. INTRODUCTION
We have implemented the above algorithms on a SGI Power Challenge shared-memory muti-processor machine with 8 processors. All algorithms base on the framework of common candidate partitioned database. One single candidate hash tree or Trie is used by all the processors, while the database is partitioned among them. Each processor traverses its local database and stores the support for itemsets separately on the shared hash tree. Finally, a master process computes the large itemsets according to the given threshold. Extensive performance studies have been carried out. It was observed that both PSM and HSM performed faster than CD-SM. In particular, HSM enjoys a very good reponse time due to its 1/0 reduction. The performance studies also showed that PSM and HSM have better speed up property than CD-SM.
I. INTRODUCTION
The rest of this paper is organized as follows. Section 2 overviews the parallel mining of association rules. Two candidate pruning techniques, distributed pruning and global pruning are described in Section 3. In Section 4, we present the PSM and HSM algorithms. Section 5 reports the result of the performance study. Finally we conclude in Section 6.
PA4RALLEL MINING OF ASSOCIATION RULES

A . Assotzataon Rules
Let I = {il, i2, ... , im} be a set of items and D be a of mining association rules is to find all the association rules whose support is larger than a given minimum support threshold and whose confidence is larger than a given minimum confidence threshold. For an itemset X, we use X sup to denote its support count in database D , which is the number of transactions in D containing X. An item-
A . Assotzataon Rules
where m i n s u p is the given minimum support threshold. For the purpose of presentation, we sometimes just use support to stand for support count of an itemset.
A . Assotzataon Rules
It has been shown that the problem of mining association rules can be decomposed into two subproblems [l] : (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, the current research has been focused on how t o efficiently solve the first subproblem.
A . Assotzataon Rules
itemsets L k are computed independently by each processor. CD repeats steps 1 -4 until no more candidate is found.
A . Assotzataon Rules
2) scan partition D, to find the local support count
X s u P ( % )
for all S E C k ;
X s u P ( % )
3) exchange {X s u p ( i ) 1 X E C k } with all other processors to get global support counts X s u p , for all X E C k ; to denote the local support of X at processor i , which is
X s u P ( % )
We also call X gl-large at processor 2, if X is globally large and locally large at processor i. For convenience, we use the term k-itemset to stand for size-k itemset, and use L k , GLb(,) to denote the set of all globally large k-itemsets and the set of all gl-large k-itemsets n t processor i, respectively. CD only applies tunction aprzorz-gen on the set L k -1 to generate the candidate sets Ck in the Ic-th iteration. In fact, after the support counts exchange in the ( k -1)-th iteration, each processor can find out not only the large itemsets L k -1 in CkPl but also the processors at which an itemset X is gl-large for any X E L k P l . By using this information, many candidates in C k can be identified to be small and hence pruned away before the next scan of the database.
B. Count Distribution Algorithm f o r Parallel Mining

A . Distributed pmning
Aprion' is the most well known serial algorithm for mining association rules [2] . It relies on the cspriori-gen function to generate the candidate sets at each iteration. CD (Count Distribution) is a parallel version of Apriori for parallel mining basing on shared-nothing multiprocessor The distributed pruning technique is derived from the observation that all subsets of any large itemsets must be gl-large simultaneously on at least one processor. For example, suppose the database is partitioned into D1 and Dz on processors 1 and 2. Further assume that both A and B are two size-1 globally large itemsets. In addition, A is gl-large at processor 1 but not processor 2, and B is gl-large at processor 2 but not processor 1. It can be shown that AB E C 2 can never be globally large. If AB is globally large, it must be globally and locally large (gllarge) at some processor. Assume it is gl-large at processor 1, then B must also be gl-large at processor 1, which is contradictory to the assumption. Similarly, AB cannot be gl-large at processor 2. Hence AB cannot be globally barrtina@example.net. In other words, if AB was globally large, then A and B must be gl-large at the same time on processor 1 or processor 2 or both of them. This observation can be genera1i.zed to the k-th iteration. Therefore, the candidates can be generated by applying function apriori-gen on each GLk-l(i), (1 5 i 5 n ) , independently.
A . Distributed pmning
The set of size-k candidates generated with this technique is equal to CGg = UY=lCGg(i), where CGg(i) = apriori..gen(GLk-l(i)). Note that the function apriori-gen is the same as that in the Apriori algorithm, but it is applied on subsets of Lk-1 rather than the whole Lk-1. Due to the combinatorial effect, the size of Cg = apriori-gen(lk-1) could be much larger than that of CGg. The above observation can be summarized by the following theorem proved in [ 5 ] .
A . Distributed pmning
Theorem 1 For k > 1, the set of all globally large kiternsets Lk is a subset of CGk = UY=lCGk(i), where
CGk(,) = apriori-gen(Gll,-l(,)).
Based on Theorem 1, we can prune away any size-k candidate such that there does not exist any processor at which all its size-(& 1) subsets are gl-large. This pruning technique is called distributed pruning.
B. Global Pruning
In the counting process, each processor keeps its local support counts for etery candidates. The local support counts are exchanged or shared after each iteration. As a result, the local support counts X F n p ( t ) , for all processor i , (1 5 i 5 n ) , are also available at every other pro- where
B. Global Pruning
is an upper bound of the global support of X. If X < minsup x ID/, then X can be pruned away. This technique is called global prunzng. Note that global pruning requires no additional information except the local support counts resulted from count exchange or sharing in the previous iteration. We can apply global pruning to the survivals of candidates after going through the distributed pruning to get the smaller candidate itemsets. That is, if the upper bound of an itemset X is found to be smaller than the support threshold, X cannot be globally large and should be removed from the set of candidate sets.
IV. PSM AND HSM ALGORITHMS

A . Parallel Maning on Shared-Memory Model Algorithm P S M )
The PSM is an enhancement of CD-SM. The main difference between them is that both the distributed pruning and global pruning are incorporated in the PSM algorithm to reduce the candidate set size. The first iteration of PSM is the same as CD-SM. Each processor scans its partition to find out local support counts of all size-1 itemsets and the master process is in charge of computing the global support counts. At the end, in addition to L1, each processor also find out the gl-large itemsets GLl(,), for 1 5 i 5 n.
A . Parallel Maning on Shared-Memory Model Algorithm P S M )
For the k-th iteration of FPM, k > 1, the program fragment at processor i, 1 5 i 5 R, is described in Fig. 2. 
1) compute candidate sets CGL(,) = Aprioii_gen(GLr_l(,));
2) prune candidates in CGk(,) by global pruning; 3) build CGq:) into the common hash tree HI"(,); 4) scan partition D, to find the local support The PSM algorithm is designed on the model of common candidate hash tree and partitioned database. Every processor can visit the shared hash tree for looking up the candidates while the database split among them. Local counter airay with length of ICkl is kept by every processor to record the local support counts. At the end of each iteration, these local counter arrays are shared by all processors. The data structure of the common hash is exactly same as used in Apriori 121.
B. Hybrid Parallel Mining on Shared-Memory Model Algorithm(HSM)
Although PSM has much less candidates than CD-SM, they have the same 1/0 cost, i.e., they scan database with the same number of passes. Under the shared-memory computing model, most machines only have serial I/o ability up to now. However, we have to face the hugh volume database in the data mining task. Thus the cost of 1/0 becomes the bottleneck. The HSM algorithm is designed to reduce the 1/0 cost. HSM retains the pruning techniques in PSM. In details, the first and second iterations of HSM is the same as PSM. Then we can get the results of L1, Lz. Obviously C3 can be generated by using Apriori-gen and pruning techniques on Lz. The subsequent steps are different from that in PSM. We continue to generate C 4 from C3 by using Apriori-gen only and from C, to C5 and so on, until no candidate is generated. A Trie as described in [4] is used to store the support counts after each processor performs one scan on its partition. Therefore, with only one pass, we can compute all large itemsets of size larger than two.
B. Hybrid Parallel Mining on Shared-Memory Model Algorithm(HSM)
Since HSM only scan database at most three passes, it incures much less 1/0 comparing with CD-SM. The other more flexible strategy in HSM is to assign a threshold for the C k . When the size of C k is less than the threshold, the algorithm then switchs from the hash tree approach to the Trie approach. 
A . Synthetic Databases Generation
We use the synthetic test data generator introduced in [2] . The database partition of each node is about 33MB in size, and the number of partitions is 8, i.e., n = 8.
A . Synthetic Databases Generation
The number of items N = 1000 and the number of maximal potentially large itemsets ILI = 1000. Table 1 shows the databases used and their properties. In it, D, is the number of transactions in each partitions, T is the average size of the transactions, and I is the average size of the itemsets. The minimum support threshold is 1% while 2% at the last two cases. We ran all CD-SM, PSM and HSM on the 5 databases. Experiments were repeated multiple times to obtain stable values. Fig. 3 shows the response times for the three parallel algorithms on the five databases. Both HSM and PSM are faster than CD-SM in all cases. It seems that the response time of the HSM is near a constant value. But this is a mere coincidence due to the adjustment on the experiment parameters including transaction number, transac- Fig. 4 shows the pruning effects. It is the ratio of the number of candidate sets with pruning over that generated by Apriori-gen only. There are much less candidate . tion average size and the minimum support threshold. itemsets generated when distributed pruning and global pruning techniques are used. It is obviously that the pruning effect is related to the data distribution among the database partitions. The expected results is that the more data skewness among the partitions, the better the pruning effect. For an extreme example, let 2 database partitions for 2 processors, if itemsets A B , AC, BC are all gl-large at both 2 processors, then neither distributed pruning nor global pruning can prune the itemset ABC out. Extensive studies on the skewness as a parameter on the pruning effect has been performed and will be reported in the future.
B. Relative Performance

C. Parallel Performance
We have investigated the performance speedup on a fixed size database with increasing number of processors and partitions. The database D700K.Tl0.14 was chosen as the dataset withthe minimum support threshold 1.0%. Fig. 5 presents the relative speedup. The result is very encouraging. Both HSM and PSM performed better speedup than CD-SM. Especially, HSM has achieved a superlinear speedup. The reason is that the pruning effect is augmented when the number of partitions is increased. Although there was the same pruning effect in PSM algorithm, it didn't present a superlinear property because there is no optimization on 1/0 reduction.
C. Parallel Performance
Another phenomenon in Fig. 5 is that speedup of the three algorithms are not linear. The reason is that the 1/0 mechanism of SGI Power challenge is not parallel. The 1/0 contention among processors increase when the number of processor increases, and hence has a negative impact on the performance.
VI. CONCLUSIONS
In this paper, we proposed two parallel algorithms PSM and HSM for mining association rules on the SGI Power Challenge shared-memory multi-processor. PSM is incorporated with two candidate pruning techniques, distributed pruning and global pruning. HSM further enhances PSM by utilizing an 1/0 reduction strategy. The experiments showed that both algorithms performed better than CD-SM. In the future work, we are interested in using dynamic candidates generation approach to further reduce the 1/0 cost and adopt an asynchronous mechanism on shared-momory parallel system to speedup the response time.

{'paper_id': '60946715', 'title': 'Efficient parallel mining of association rules on shared-memory multiple-processor machine', 's2_url': 'https://api.semanticscholar.org/CorpusID:60946715', 'source': 'S2ORC'}