GPApriori: GPU-Accelerated Frequent Itemset Mining

In this paper we describe GPA priori, a GPU-accelerated implementation of Frequent Item set Mining (FIM). We tested our implementation with an Nvidia Tesla T10 graphic processor and demonstrate up to 100× speedup as compared with several state-of-the-art FIM algorithms on a CPU. In order to map the Apriori algorithm onto the SIMD execution model, we have designed a "static bitset" memory structure to represent the input database. This data structure improves upon the traditional approach of the vertical data layout in state-of-the art Apriori implementations. In our implementation, we perform a parallelized version of the support counting step on the GPU. Experimental results show that GPA priori consistently outperforms CPU-based Apriori implementations. Our results demonstrate the potential for GPGPUs in speeding up data mining algorithms.