Tree Projection-Based Frequent Itemset Mining on Multicore CPUs and GPUs

• George Teodoro UFMG
• Nathan Mariano UFMG
• Wagner Meira Jr. UFMG
• Renato Ferreira UFMG

Resumo

Frequent itemset mining (FIM) is a core operation for several data mining applications as association rules computation, correlations, document classification, and many others, which has been extensively studied over the last decades. Moreover, databases are becoming increasingly larger, thus requiring a higher computing power to mine them in reasonable time. At the same time, the advances in high performance computing platforms are transforming them into hierarchical parallel environments equipped with multi-core processors and many-core accelerators, such as GPUs. Thus, fully exploiting these systems to perform FIM tasks poses as a challenging and critical problem that we address in this paper. We present efficient multi-core and GPU accelerated parallelizations of the Tree Projection, one of the most competitive FIM algorithms. The experimental results show that our Tree Projection implementation scales almost linearly in a CPU shared-memory environment after careful optimizations, while the GPU versions are up to 173 times faster than standard the CPU version.

Palavras-chave: Itemsets, Graphics processing unit, Instruction sets, Parallel processing, Data mining, Multicore processing