A Scalable Multi-Strategy Algorithm for Counting Frequent Sets
Salvatore Orlando, Paolo Palmerini, Raffaele Perego, Fabrizio Silvestri · 2002
In this paper we present DCI, a new data mining algorithm for frequent set counting. We also discuss in depth the parallelization strategies used in the design of ParDCI, the distributed and multi-threaded algorithm derived from DCI. Multiple heuristics strategies are adopted within DCI, so that the algorithm is able to adapt its behavior not only to the features of the specific computing platform, but also to the features of the dataset being processed. Our approach turned out to be highly scalable and very e#cient for mining both short and long patterns present in real and synthetically generated datasets. The experimental results showed that DCI outperforms others previously proposed algorithms under a variety of conditions. ParDCI, the parallel version of DCI, is explicitly devised for targeting clusters of SMP nodes: shared memory and message passing paradigms were used at intra- and inter-node level, respectively. Due to the broad similarity between DCI and Apriori , we were able to adapt e#ective parallelization strategies previously proposed for Apriori .