Frequent itemset mining on graphics processors
Hong Kong University of Science and Technology
Proceedings of the Fifth International Workshop on Data Management on New Hardware DaMoN ’09
@conference{fang2009frequent,
title={Frequent itemset mining on graphics processors},
author={Fang, W. and Lu, M. and Xiao, X. and He, B. and Luo, Q.},
booktitle={Proceedings of the Fifth International Workshop on Data Management on New Hardware},
pages={34–42},
year={2009},
organization={ACM}
}
We present two efficient Apriori implementations of Frequent Itemset Mining (FIM) that utilize new-generation graphics processing units (GPUs). Our implementations take advantage of the GPU’s massively multi-threaded SIMD (Single Instruction, Multiple Data) architecture. Both implementations employ a bitmap data structure to exploit the GPU’s SIMD parallelism and to accelerate the frequency counting operation. One implementation runs entirely on the GPU and eliminates intermediate data transfer between the GPU memory and the CPU memory. The other implementation employs both the GPU and the CPU for processing. It represents itemsets in a trie, and uses the CPU for trie traversing and incremental maintenance. Our preliminary results show that both implementations achieve a speedup of up to two orders of magnitude over optimized CPU Apriori implementations on a PC with an NVIDIA GTX 280 GPU and a quad-core CPU.
December 21, 2010 by hgpu
