基于PC集群的并行FP-Growth算法的研究与实现

作     者：王登平 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：王保保

授予年度：2011年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：FP-Growth算法 集群 并行计算 关联规则 硬件异构并行计算平台 

摘      要：FP-Growth算法是当前挖掘频繁项集算法中应用最广，并且不需要产生候选项集的频繁项集挖掘算法。它通过对源数据库的两次扫描，将全部数据项信息压缩到一个称为FP-tree的数据结构中，将数据库频繁模式的挖掘问题转化成挖掘FP-tree的问题。然而，在处理海量数据时，生成的FP-tree数据结构极为复杂，生成频繁集并挖掘频繁项集生成强关联规则过程，对内存和处理器要求极高。并行算法可以将计算任务合理地分配集群中的各个计算节点，因此对并行FP-Growth算法的研究在频繁项集挖掘中具有十分重要的现实意义。 本文深入研究了并行计算理论、高性能计算集群和FP-Growth算法，对并行计算机的体系结构、并行算法的设计方法、高性能计算集群的创建技术和FP-Growth算法各个步骤有良好的理解。为了实现FP-Growth算法的并行化，本文对并行FP-Growth的一些典型算法进行了分析，发现它们主要是基于硬件同构并行计算平台，对算法中计算节点负载均衡在硬件异构并行计算平台并未加于考虑，因此，这些算法在硬件异构并行计算平台中的性能不佳。为了实现PC集群下的并行FP-Growth算法，本文设计和实现了一个高性能计算集群，提出并实现了一种在硬件异构计算平台上的并行FP-Growth算法。实验结果表明，使用本文所提出的算法后，在仅有三个计算节点的集群环境中加速比可达到2.3以上。