An efficient algorithm for mining association rules for large itemsets in large databases: from sequential to parallel

This paper addresses three issues: (a) development of a new algorithm for m ining association rules efficiently from large databases in both sequential and distributed environments, (b) parallelization of this new algorithm to enhance performance gain by distributed parallelism, and (c) improvement o f this gain by properly steered scalability. The new algorithm is derived f rom the traditional Apriori approach by adding features to improve mining p erformance. These features include the binary encoding mechanism and its lo garithmic decoding counterpart. There is a need to parallelize the mining p rocess only when the overlay structure for the binary encoded structure for the database is too big and requires frequent time-consuming data swapping during the mining process. The scale of the parallelization, however, shou ld be tuned down gradually by scalability so that the computation-to-commun ication ratio can be kept at a reasonable level to maintain the benefit fro m parallelism.