Journal of South China University of Technology (Natural Science Edition) ›› 2014, Vol. 42 ›› Issue (1): 135-141.doi: 10.3969/j.issn.1000-565X.2014.01.023

• Computer Science & Technology • Previous Articles     Next Articles

FP- Growth Algorithm Based on Boolean Matrix and MapReduce

Chen Xing- shu Zhang Shuai Tong Hao Cui Xiao- jing   

  1. College of Computer,Sichuan University,Chengdu 610065,Sichuan,China
  • Received:2013-05-06 Revised:2013-10-22 Online:2014-01-25 Published:2013-12-01
  • Contact: 陈兴蜀(1968-)，女，教授，博士生导师，主要从事信息安全、计算机网络研究． E-mail:chenxsh@scu.edu.cn
  • About author:陈兴蜀(1968-)，女，教授，博士生导师，主要从事信息安全、计算机网络研究．
  • Supported by:

    国家自然科学基金面上项目(61272447)

PDF

979

Abstract:

Association rules mining is an important part of data mining.In order to improve the efficiency of associ-ation rules mining,an FP- Growth algorithm based on Boolean matrix and MapReduce,which is marked as BPFP,is proposed,with its time and space complexity being also analyzed.In BPFP algorithm,Hadoop framework andBoolean matrix are used to reduce the number of scans of transaction data,and twice Map- Reduce is adopted tomine frequent item sets.Experimental results on multiple data sets show that the improved FP- Growth algorithm issuperior to the original one due to its high execution efficiency and speedup.

Key words: data mining, association rules, Boolean matrix, MapReduce, FP- Growth algorithm