Session:

Knowledge Representation, Decision Support and Expert Systems
Tuesday, March 02, 2004, 11.10 – 11.30

Session Chair:
Vice Chair:

A. Dobnikar
M. Savoji

Paper Title:

Dynamic Itemset Counting in PC Cluster Based Association Rule Mining

Author(s):

F. Kovács, Budapest University of Technology and Economics, Hungary
I Vajk, Budapest University of Technology and Economics, Hungary

Abstract:

One of the most important problems in data mining is association rule mining. It requires very large computation and I/O traffic capacity. For that reason there are several parallel mining algorithms, which can take advantage of the performance of the cluster systems. These algorithms are optimized and developed on supercomputer platforms, but nowadays the capacity of PC keeps the possibility to build cluster systems cheaper. Usage of PC cluster systems raises some issues about the optimization of the distributed mining algorithms, especially the cost of the node to node communication and cost of the synchronization. The communication costs of currently used main distributed association rule mining algorithms depends on the number of nodes with O(n2) complexity. The node synchronization is also a very important issue. The current algorithms contain too many synchronization points and this can cause performance decrease, especially in PC cluster environment. In this paper a new distributed association rule mining algorithm is introduced, which is based on dynamic itemset counting. The communication costs of this newly developed algorithm is O(n) and the nodes can work asynchronously.