Fast Frequent Pattern Mining without Candidate Generations on GPU by Low Latency Memory Allocation
Yuchen Wu, Mi-Yen Yeh, Tei‐Wei Kuo · 2019
In this work, we propose a GPU-accelerated algorithm for frequent pattern(FP) mining without candidate generation. We observe that the existing FP-growth algorithm has critical characteristics unsuitable for GPU, including the tree data structure, deep recursion and heavy dynamic memory allocations. By utilizing iterative execution and collectively allocating memory on GPU, our proposed method significantly reduce the latency caused by large memory allocations of original FP-growth. Experiment results show that our solution outperforms baselines, including sequential FP-growth with CPU only and existing GPU-accelerated Apriori and FP-growth, on various data sets with a significant speedup, from several times to hundred times.