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

发布时间：2020-06-30 00:28

【摘要】：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以上。
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2011
【分类号】：TP311.13;TP338.6

【参考文献】