资源描述：
《一种基于图形处理器的频繁模式挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第10期白洪涛等：一种基于图形处理器的频繁模式挖掘算法1623第10期白洪涛等：一种基于图形处理器的频繁模式挖掘算法1623第10期白洪涛等：一种基于图形处理器的频繁模式挖掘算法1623一种基于图形处理器的频繁模式挖掘算法*白洪涛1,2，欧阳丹彤1,2，何丽莉1,2（1 吉林大学计算机科学与技术学院 长春 130012；2 吉林大学符号计算与知识工程教育部重点实验室 长春 130012）摘 要：频繁模式挖掘是数据挖掘的核心问题。传统上，频繁模式并行挖掘主要是在集群上进行的，较少涉及共享内存多处理系统上的并行挖掘。基于广度优先搜索和
2、直接计数策略研究了一种并行挖掘方法,并在图形处理器(graphicsprocessingunit,GPU)最新统一计算设备架构CUDA(computeunifieddevicearchitecture)下进行了实现。GPU-basedFPMA用CPU控制搜索进程；在GPU的多处理器上，采用数据划分的计算策略，以适合GPU的顺序数据流方式计数，并根据候选项的长度动态剪枝事务数据集。实验结果表明，GPU-basedFPMA比CPU版本平均加速了10倍以上。关键词：关联规则；频繁模式；图形处理器；并行计算；统一计算设备架构中图分类号：T
3、P311.1 文献标识码：A 国家标准学科分类代码：520.3020GPU-basedfrequentpatternminingalgorithmBaiHongtao1,2,OuyangDantong1,2,HeLi1i1,2（1CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012,China;2KeyLaboratoryofSymbolicComputationandKnowledgeEngineeringofMinistryofEduca
4、tion,JilinUniversity,Changchun130012,China）Abstract：Frequentpatternminingisanimportantissueindataminingarea.Traditionally,parallelfrequentpatternminingiscarriedoutinPCclusters,andseldomrelatedtomulti-processorsormassivecoreswithsharedmemories.Inthispaper,weproposeapar
5、allelfrequentpatternminingalgorithmsuitableforGPU(graphicsprocessingunit)basedonwidthsearchanddirectsupportstrategy.Itisimplementedundercomputeunifieddevicearchitecture(CUDA)ofGPU.Inthisalgorithm,CPUtakeschargeofsearchprocessandGPUisresponsibleforcountingusingdatapart
6、ition.Inaddition,transactionsaredynamicallyprunedaccordingtothelength(k)ofcandidatefrequentitemsets.PerformanceanalysisshowsthatGPU-basedFPMAreachesanaveragespeedasfastasthatof10timesofCPU-basedcounterpart.Keywords：associationrule;frequentpattern;GPU;parallelcomputing
7、;CUDA第10期白洪涛等：一种基于图形处理器的频繁模式挖掘算法20831 引 言收稿日期：2008-11 ReceivedDate：2008-11*基金项目：国家自然科学基金重大项目(60496320,60496321)、国家自然科学基金(60773097,60873148)资助项目自关联规则挖掘[1]的概念被提出以来,频繁模式挖掘算法的发展得到了相当多的关注,在关联规则挖掘、推理数据库和查询扩展等方向应用众多。面对日益增长、特征各异的数据集,算法面临的一个基本问题是如何保证高效运行。基于对算法效率瓶颈的理解和问题解决方案,
8、产生了多种代表性算法,如Apriori[2]、Partition[3]、Eclat[4]、Fp-growth[5]等。其中除Fp-growth是一种典型的模式增长类算法,其他3种都是候选-计数模型类算法。其后,诸多算法对原始算法或进行改进,或衍生变
