Title :
Parallel frequent patterns mining algorithm on GPU
Author :
Zhou, Jiayi ; Yu, Kun-Ming ; Wu, Bin-Chang
Author_Institution :
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Abstract :
Extraction of frequent patterns from a transactional database is a fundamental task in data mining. Its applications include association rules, time series, etc. The Apriori approach is a commonly used generate-and-test approach to obtain frequent patterns from a database with a given threshold. Many parallel and distributed methods have been proposed for frequent pattern mining (FPM) to reduce computation time. However, most of them require a Cluster system or Grid system. In this study, a graphic processing unit (GPU) was used to perform FPM with a GPU-FPM to speed-up the process. Because of GPU hardware delimitations, a compact data structure was designed to store an entire database on GPU. In addition, MemPack and CLProgram template classes were also designed. Two datasets with different conditions were used to verify the performance of GPU-FPM. The experimental results showed that the speed-up ratio of GPU-FPM can achieve 14.857 with 16 times of threads.
Keywords :
computer graphic equipment; coprocessors; data mining; data structures; parallel algorithms; pattern clustering; CLProgram template classes; GPU; MemPack template classes; association rule; cluster system; data mining; data structure; distributed method; frequent pattern mining; generate and test approach; graphic processing unit; grid system; parallel algorithm; parallel method; pattern extraction; time series; transactional database; Graphics processing unit; Itemsets; OpenCL; frequent pattern mining; graphic processing unit (GPU); parallel processing;
Conference_Titel :
Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on
Conference_Location :
Istanbul
Print_ISBN :
978-1-4244-6586-6
DOI :
10.1109/ICSMC.2010.5641778