Abstract

Due to the huge increase in the number and dimension of available
databases, efficient solutions for counting frequent sets are
nowadays very important within the Data Mining community. Several
sequential and parallel algorithms were proposed, which in many
cases exhibit excellent scalability.  In this paper we present
ParDCI, a distributed and multithreaded algorithm for counting the
occurrences of frequent sets within transactional
databases. ParDCI is a parallel version of DCI (Direct Count &
Intersect), a multi-strategy algorithm which is able to adapt its
behavior not only to the features of the specific computing
platform (e.g. available memory), but also to the features of the
dataset being processed (e.g. sparse or dense datasets).  ParDCI
enhances previous proposals by exploiting the highly optimized
counting and intersection techniques of DCI, and by relying on a
multi-level parallelization approach which explicitly targets
clusters of SMPs, an emerging computing platform.  We focused our
work on the efficient exploitation of the underlying architecture.
Intra-Node multithreading effectively exploits the memory
hierarchies of each SMP node, while Inter-Node parallelism exploits
smart partitioning techniques aimed at reducing communication
overheads. In depth experimental evaluations demonstrate that
ParDCI reaches nearly optimal performances under a variety of
conditions.