An adaptive algorithm for mining association rules on shared-memory parallel machines

Mining association rules from large databases is very costly. We propose to develop parallel algorithms for this task on shared-memory multiprocessor (SMP). All proposed parallel algorithms for other paradigms follow the conv entional level-wise approach: they need as many iterations as the length of the maximum large itemset. To make matter worse, they impose a synchroniza tion in every iteration which would cause serious I/O contention on shared- memory parallel system. An adaptive asynchronous parallel mining algorithm APM has been proposed for SMP. All processors generate candidates dynamical ly and count itemset supports independently without synchronization. Two op timization techniques have been proposed for the reduction of database scan ning and the number of candidates. The algorithm APM has been implemented o n a Sun Enterprise 4000 shared-memory multiprocessor with 12 nodes. The exp eriments show that the optimizations have very good effects and APM has a s ubstantial lead in performance over other proposed level-wise algorithms.