An Hybrid Multi-Core/GPU-Based Mimetic Algorithm for Big Association Rule Mining

Abstract

This paper addresses the problem of big association rule mining using an evolutionary approach. The mimetic method has been successfully applied to small and medium size databases. However, when applied on larger databases, the performance of this method becomes an important issue and current algorithms have very long execution times. Modern CPU/GPU architectures are composed of many cores, which are massively threaded and provide a large amount of computing power, suitable for improving the performance of optimization techniques. The parallelization of such method on GPU architecture is thus promising to deal with very large datasets in real time. In this paper, an approach is proposed where the rule evaluation process is parallelized on GPU, while the generation of rules is performed on a multi-core CPU. Furthermore, an intelligent strategy is proposed to partition the search space of rules in several independent sub-spaces to allow multiple CPU cores to explore the search space efficiently and without performing redundant work. Experimental results reveal that the suggested approach outperforms the sequential version by up to at 600 times for large datasets. Moreover, it outperforms the-state-of-the-art high performance computing based approaches when dealing with the big WebDocs dataset.