GPApriori: GPU-Accelerated Frequent Itemset Mining
Department of Computer Science, University of South Carolina, Columbia, SC, U.S.
IEEE International Conference on Cluster Computing (CLUSTER), 2011
@inproceedings{zhang2011gpapriori,
title={GPApriori: GPU-Accelerated Frequent Itemset Mining},
author={Zhang, F. and Zhang, Y. and Bakos, J.},
booktitle={Cluster Computing (CLUSTER), 2011 IEEE International Conference on},
pages={590–594},
year={2011},
organization={IEEE}
}
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 100x 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.
January 24, 2012 by hgpu
