A scalable multi-strategy algorithm for counting frequent sets

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 efficient 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 effective parallelization strategies previously proposed for Apriori. As a result, ParDCI reaches near optimal speedups.