基于位存储Tid的CPU并行化Eclat算法

doi:10.19678/j.issn.1000-3428.0049259

计算机工程 ›› 2018, Vol. 44 ›› Issue (12): 79-84. doi: 10.19678/j.issn.1000-3428.0049259

基于位存储Tid的CPU并行化Eclat算法

孙宗鑫,张桂芸

天津师范大学计算机与信息工程学院,天津 300387

收稿日期:2017-11-10 出版日期:2018-12-15 发布日期:2018-12-15
作者简介:孙宗鑫(1991—),男,硕士研究生,主研方向为数据挖掘、大数据分析;张桂芸(通信作者),教授。
基金资助:
国家自然科学基金面上项目(61572358);天津市自然科学基金面上项目(16JCYBJC23600)

CPU Parallelization Eclat Algorithm Based on Bit Storage Tid

SUN Zongxin,ZHANG Guiyun

College of Computer and Information Engineering,Tianjin Normal University,Tianjin 300387,China

Received:2017-11-10 Online:2018-12-15 Published:2018-12-15

摘要/Abstract

摘要：

Eclat算法采用垂直数据表示方式且无需复杂的数据结构,然而在挖掘频繁项目集过程中,交集计数的生成方式造成内存大量消耗和挖掘效率下降。为此,在分析Eclat算法及其现有改进算法基础上,提出一种位存储事务标识(Tid)的CPU并行化Eclat算法。该算法使用二进制位形式存储项目的Tid,将挖掘频繁项目集的任务分配到CPU各个线程,最大限度地提高CPU的运算性能。实验结果表明,该算法能在降低内存使用的同时,提高频繁项目集的挖掘效率。

关键词: 频繁项目集挖掘, Eclat算法, 位存储, CPU并行化, 存储优化

Abstract:

The Eclat algorithm uses vertical data representation and does not require complex data structures.However,the intersection count generation mode causes a large amount of memory consumption and low mining efficiency in the process of mining frequent itemsets.Therefore,based on the analysis of Eclat algorithm and its existing improved algorithm,a CPU parallelization Eclat algorithm for bit storing Transaction identifier(Tid) is proposed.The algorithm uses the binary bit form to store the Tid of the project,and distributes the tasks of mining frequent itemsets to each thread of the CPU,maximizing the computing performance of the CPU.Experimental results show that the algorithm can improve the mining efficiency of frequent itemsets while reducing memory usage.

Key words: Frequent Itemset Mining(FIM), Eclat algorithm, bit storage, CPU parallelization, storage optimization

中图分类号:

TP312

孙宗鑫,张桂芸. 基于位存储Tid的CPU并行化Eclat算法[J]. 计算机工程, 2018, 44(12): 79-84.

SUN Zongxin,ZHANG Guiyun. CPU Parallelization Eclat Algorithm Based on Bit Storage Tid[J]. Computer Engineering, 2018, 44(12): 79-84.

http://www.ecice06.com/CN/Y2018/V44/I12/79

参考文献

［1］AGRAWAL R,SRIKANT R.Fast algorithm for mining association rules in large database［C］//Proceedings of International Conference on Very Large Data Bases.Santiago,Chile:［s.n.］,1994:487-499.
［2］PARK J S,CHEN M S,YU P S.An effective hash-based algorithm for mining association rules［C］//Proceedings of 1995 ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,1995:175-186.
［3］ZAKI M J.Scalable algorithms for association mining［J］.IEEE Transactions on Knowledge & Data Engineering,2000,12(3):372-390.
［4］HAN J,PEI J,YIN Y.Mining frequent patterns without candidate generation［J］.ACM SIGMOD Record,2000,29(2):1-12.
［5］熊忠阳,陈培恩,张玉芳.基于散列布尔矩阵的关联规则Eclat改进算法［J］.计算机应用研究,2010,27(4):1323-1325.
［6］冯培恩,刘屿,邱清盈,等.提高Eclat算法效率的策略［J］.浙江大学学报(工学版),2013,47(2):223-230.
［7］张步忠,程玉胜,王则林.基于片上多核的频繁项集并行挖掘算法［J］.计算机科学,2014,41(3):55-58.
［8］YU X,WANG H.Improvement of Eclat algorithm based on support in frequent itemset mining［J］.Journal of Computers,2014,9(9).
［9］KAUR M,GARG U,KAUR S.Advanced Eclat algorithm for frequent itemsets generation［J］.Inter-national Journal of Applied Engineering Research,2015,10(9):23263-23279.
［10］WANG K,QI Y,FOX J J,et al.Association rule mining with the micron automata processor［C］//Proceedings of Parallel and Distributed Processing Symposium.Washington D.C.,USA:IEEE Press,2015:689-699.
［11］DIAS V,MOREIA R,MEIRA W,et al.Diagnosing performance bottlenecks in massive data parallel programs［C］//Proceedings of IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.Washington D.C.,USA:IEEE Press,2016:273-276.
［12］ZOIS V,PANANGANAN A,PRASANNA V.Accelerating support count for association rule mining on GPUs［C］//Proceedings of IEEE International Parallel and Distributed Processing Symposium.Washington D.C.,USA:IEEE Press,2016:1423-1432.
［13］KHOLOD I,SHOROV A,GORLATCH S.A functional approach to parallelizing data mining algorithms in Java［C］//Proceedings of International Conference on Parallel Computing Technologies.Berlin,Germany:Springer,2017:459-472.
［14］HEATON J.Comparing dataset characteristics that favor the Apriori,Eclat or FP-growth frequent itemset mining algorithms［EB/OL］.［2017-02-21］.http://www.xcdsystem.com/Southeastcon.
［15］严健康,陈更生.基于CPU/GPU异构资源协同调度的改进H-Storm［J］.计算机工程,2018,44(4):1-11.
［16］李丽娜,魏晓辉,李翔,等.流数据处理中负载突发感知的弹性资源分配［J］.计算机学报,2018,41(10):2193-2208.
［17］ZHANG C,ZHANG X,TIAN P.An approximate approach to frequent itemset mining［C］//Proceedings of the 2nd IEEE International Conference on Data Science in Cyberspace.Washington D.C.,USA:IEEE Press,2017:68-73.

[1]	王路辉,王桂玲. 基于车牌识别流数据的伴随车辆发现算法[J]. 计算机工程, 2017, 43(8): 193-199.
[2]	李进文，安博文. 基于DM642的光纤中心定位算法优化[J]. 计算机工程, 2014, 40(4): 305-308.
[3]	张玉芳, 熊忠阳, 耿晓斐, 陈剑敏. Eclat算法的分析及改进[J]. 计算机工程, 2010, 36(23): 28-30.
[4]	张帆;窦　勇;邬贵明. 基于C6000的滑动窗口图像处理算法存储优化[J]. 计算机工程, 2009, 35(1): 46-48.
[5]	谢俊;刘海涛;管海兵. SmallFS的研究与实现[J]. 计算机工程, 2008, 34(17): 44-46.
[6]	徐宁;史册;陈梅丽. 基于嵌入式处理器的H .264编码器的存储优化[J]. 计算机工程, 2006, 32(23): 268-270.

选择文件类型/文献管理软件名称

选择包含的内容

基于位存储Tid的CPU并行化Eclat算法

CPU Parallelization Eclat Algorithm Based on Bit Storage Tid

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于位存储Tid的CPU并行化Eclat算法

CPU Parallelization Eclat Algorithm Based on Bit Storage Tid

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价