Evaluation of connected-component labeling algorithms for distributed-memory systems
Evaluation of connected-component labeling algorithms for distributed-memory systems
复制标题
DOI：
10.1016/j.parco.2015.02.005
复制
发表时间：
2015-05-01
影响因子：
1.4
通讯作者：
Karypis, G.
中科院分区：
文献类型：
--
作者：
Iverson, J.;Kamath, C.;Karypis, G.
连接组件标记是广泛应用的关键步骤，例如社会网络中的社区检测和大规模并行科学模拟中的连贯结构识别。文献中描述了几种分布式内存连接组件算法；然而，关于它们的稳定性分析却很少。本文提出了五种算法的理论和实验结果：三种算法是先前方法的直接实现，一种算法是先前方法的实现，该方法经过优化以减少通信，另一种算法是基于图收缩的新方法。在弱尺度下，对于某些类型的图，图收缩算法的尺度一致性优于其他四种算法。此外，它比其中两种替代方法使用的内存少得多，并且与其他两种方法在内存方面的顺序相同。(C) 2015 Elsevier B.V.版权所有
Connected component labeling is a key step in a wide-range of applications, such as community detection in social networks and coherent structure identification in massively-parallel scientific simulations. There have been several distributed-memory connected component algorithms described in literature; however, little has been done regarding their stalability analysis. Theoretical and experimental results are presented for five algorithms: three that are direct implementations of previous approaches, one that is an implementation of a previous approach that is optimized to reduce communication, and one that is a novel approach based on graph contraction. Under weak scaling and for certain classes of graphs, the graph contraction algorithm scales consistently better than the four other algorithms. Furthermore, it uses significantly less memory than two of the alternative methods and is of the same order in terms of memory as the other two. (C) 2015 Elsevier B.V. All rights reserved.