Performance study of distributed Apriori-like frequent itemsets mining
Performance study of distributed Apriori-like frequent itemsets mining
复制标题
DOI：
10.1007/s10115-009-0205-3
复制
发表时间：
2010-04
影响因子：
2.7
通讯作者：
Lamine M. Aouad;Nhien-An Le-Khac;Mohand Tahar Kechadi
中科院分区：
文献类型：
--
作者：
Lamine M. Aouad;Nhien-An Le-Khac;Mohand Tahar Kechadi
在本文中，我们重点关注基于分布式 Apriori 的频繁项集挖掘。我们提出了一种新的分布式方法，该方法考虑了该算法的固有特征。我们研究了该算法的分布方面，并通过分析和实验研究将所提出的方法与经典的 Apriori 式分布式算法进行了比较。我们发现，在广泛的条件和数据集下，分布式 Apriori 类算法的性能与全局剪枝策略无关，因为局部 Apriori 生成的性能通常表现为低水平候选集频率相对较高的成功率，在某个阶段切换到非常低的速率，并且经常降至零。这意味着经典分布式方案中的中间通信步骤和远程支持计数计算和收集在本地计算效率低下，从而限制了全局性能。我们的性能评估是使用 Condor 系统及其工作流程管理器 DAGMan 在大型工作站集群上完成的。结果表明，与典型的分布式 Apriori 创建算法相比，所提出的方法极大地提高了性能并实现了良好的可扩展性。
In this article, we focus on distributed Apriori-based frequent itemsets mining. We present a new distributed approach which takes into account inherent characteristics of this algorithm. We study the distribution aspect of this algorithm and give a comparison of the proposed approach with a classical Apriori-like distributed algorithm, using both analytical and experimental studies. We find that under a wide range of conditions and datasets, the performance of a distributed Apriori-like algorithm is not related to global strategies of pruning since the performance of the local Apriori generation is usually characterized by relatively high success rates of candidate sets frequency at low levels which switch to very low rates at some stage, and often drops to zero. This means that the intermediate communication steps and remote support counts computation and collection in classical distributed schemes are computationally inefficient locally, and then constrains the global performance. Our performance evaluation is done on a large cluster of workstations using the Condor system and its workflow manager DAGMan. The results show that the presented approach greatly enhances the performance and achieves good scalability compared to a typical distributed Apriori founded algorithm.