Hits:

Indexed by:会议论文

Date of Publication:2018-01-01

Included Journals:CPCI-S

Page Number:649-654

Key Words:Frequent itemset mining; Association rule mining; GPU Computing; Apriori; CUDA; Parallel Algorithms

Abstract:As the core methodology of implementing association rules mining, frequent itemsets mining is used to extract frequent itemsets from items in a large database of transactions. In this paper, we proposed Dynamic queue & Deep Parallel Apriori (D2P-Apriori), a parallel frequent itemset mining algorithm on GPU to satisfy the high-performance requirement. The contributions of D2P-Apriori include as follows. The dynamic queue with bitmap is improved upon the vertical data structure to deal with the problem that the required memory for sparse data may exceed the size of GPU global memory. The Graph-join way is devised to adapt GPU architecture for candidate generation method. And the improved data structure also contributes to the significantly accelerated performance in support counting method on GPU. The implementation of this algorithm achieves the deep and comprehensive parallelization. Our parallel implementation on GeForce GTX 1080 graphic processor outperforms several state-of-the-art frequent itemset mining algorithms on CPU, up to 63x speedup ratio can be obtained on large dataset.