Parallelizing Apriori Algorithm using Open MP

Nilesh Sadashivrao Korde, Shailendra W. Shende

Abstract


An Association rule mining used for finding frequent item sets thus generating rules from the frequent item sets. Finding frequent itemsets is more expensive in terms of CPU power and computing resources utilization. Apriori Algorithm is used for high dimensionality on massively large data sets. Parallelism reduces the time required for serial processing. Parallel computing can be applied for mining of association rules. Parallel apriori algorithm focus on parallelizing the process of frequent item set discovery. The computation of frequent item sets mainly consists of creating the candidates and counting them. The parallel frequent itemsets mining algorithms addresses the issue of distributing the candidates among processors such that their counting and creation is effectively parallelized. In this paper we have Implemented Apriori Algorithm in serial and parallel on a quad core processor and compared their performance with respect to time.

Keywords: Multi-core, parallelism, Apriori, data mining, open MP


Full Text:

PDF

References


Han and Micheline Kamber, Data Mining Concepts and Techniques 2nd Edn. Morgan Kaufmann Publishers: San Francisco; 2006.

Recent Trends in Parallel Computing

Volume 1, Issue 1

__________________________________________________________________________________________

RTPC (2014) 1-5 © STM Journals 2014. All Rights Reserved Page 5

Ying Liu, Fuxiang Gao. Parallel Implementations of Image Processing Algorithms on Multi-Core. Fourth International Conference on Genetic and Evolutionary Computing, 2010 IEEE, 71–74p.

Agrawal R, Srikant R, “Fast Algorithms for Mining Association Rules” In: Proceedings of the 1994 International Conference on Very Large Data Bases (VLDB‟94), Santiago, Chile; 1994. 487–499p.

Anuradha.T, Satya Pasad R and S N Tirumalarao. Parallelizing Apriori on Dual Core using OpenMP. International Journal of Computer Applications: Published by Foundation of Computer Science, New York, USA; April 2012; 43(24):33–39p.

Kyung Min Lee, Tae Houn Song, Seung Hyun Yoon, Key Ho Kwon, Jae Wook Jeon. OpenMP Parallel Programming Using Dual-Core Embedded System. 11th International Conference on Control, Automation and Systems Oct. 26–29, 2011, in KINTEX, Gyeonggi-do, Korea, 762–766p.

Anuradha.T, Satya Prasad. Parallelizing Apriori on Hyper-Threaded Multi-Core Processor. International Journal of Advanced Research in Computer Science and Software Engineer. June 2013; (3) 6.

Ketan D. Shah, Dr. (Mrs.) Sunita Mahajan. Performance Analysis of Parallel Apriori on Heterogeneous Nodes. International Conference on Advances in Computing, Control, and Telecommunication Technologies, 2009 IEEE, 42–44p.

Zhong Zheng, Xuhao Chen, Zhiying Wang, Li Shen, Jiawen Li. Performance Model for OpenMP Parallelized Loops. International Conference on Transportation, Mechanical, and Electrical Engineering (TMEE), Changchun; China: December 16–18, 2011 IEEE, 383–387pp.

Chao-Tung Yang, Tzu- Chieh Chang, Hsien-Yi Wang, William C.C. Chu, Chih- Hung Chang. Performance Campion with OpenMP Parallelization for Multi-core Systems. Ninth IEEE International Symposium on Parallel and Distributed

Processing with Applications, 2011 IEEE, 232–237p.

Tim Mattson and Larry Meadows. “A’ Hands-on’ Introduction to OpenMP” Intel Corporation.

Anuradha.T, Dr.Satya Prasad.R, Dr.Tirumala Rao.S.N Performance Evaluation of Apriori with Memory Mapped Files. International Journal of Computer Science; (10); 1: January 2003.

Kent Milfeld. “Introduction to Programming with OpenMP”; Texas Advanced Computing Center (TACC): February 6th 2012.

“OpenMP Application Program Interface”; Version 3.0: May 2008.

Multi-core Processor Wikipedia [Available] en.wikipedia.org/wiki/Multi-core Processor.

Blaise Barney, Lawrence Livermore. Introduction to Parallel Computing. https://computing.llnl.gov/tutorials/parallel_comp/.

Frank Willmore. “Introduction to Parallel Computing”, February 6, 2012.


Refbacks

  • There are currently no refbacks.