Parallel Association Rule Mining by Data De-Clustering to Support Grid Computing
Frank S. C. Tseng, Pey-Yen Chen · 2005
Most of the association rule mining algorithms suffer from the time-consuming elaboration on finding all candidates that fit the subjective conditions. We believe the most effective way is to develop parallel algorithms to promote the performance. However, prior parallel architectures and algorithms suffer from overhead in inter-site communications or requiring large number of space to maintain the local support counts of a large number of candidate sets. In this paper, we propose a parallel approach, which absolutely eliminates the inter-site communication cost for the most influential Apriori algorithm or its variations. The merit makes our approach to be easily deployed in a grid computing environment. Our work is based on the idea of data de-clustering, such that the transaction database is de-clustered into partitions for all participating sites. That guarantees all subgroups are not only quite similar to each other, but also quite similar to the original group. To balance the workload of the most time-consuming subtasks (i.e., the candidate itemsets generation process) of all participating sites, elements in the frequent 1-itemset are dispatched in row-prime order to each processor to execute in parallel. We have conducted experiments to show that the result obtained by our approach is almost the same as that obtained by running the Apriori algorithm on a single site. However, if there are m processors executed in our parallel approach, then the total speed up can be promoted up to m2, which makes our work a very efficient and effective approach.