HDRF: Stream-Based Partitioning for Power-Law Graphs
HDRF: Stream-Based Partitioning for Power-Law Graphs
复制标题
DOI：
10.1145/2806416.2806424
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
F. Petroni;Leonardo Querzoni;Khuzaima S. Daudjee;Shahin Kamali;Giorgio Iacoboni
中科院分区：
文献类型：
--
作者：
F. Petroni;Leonardo Querzoni;Khuzaima S. Daudjee;Shahin Kamali;Giorgio Iacoboni
平衡的图形分区是一个基本问题，随着分布式图解（DGC）框架的出现，它正在引起人们的注意。在这些框架中，分区策略起着重要作用，因为它可以驱动计算节点之间的通信成本和工作量平衡，从而影响系统性能。但是，现有解决方案仅部分利用了现实世界中常见的自然图的关键特征：它们高度偏斜的幂律学位分布。在本文中，我们提出了首先复制的高度（HDRF），这是一种新型的流顶点切割算法，该算法有效地利用了偏斜的分布，通过明确考虑放置决策中的顶点程度。我们通过分析和实验评估合成图和现实图表的HDRF，并表明它在分区质量方面的表现优于所有现有算法。
Balanced graph partitioning is a fundamental problem that is receiving growing attention with the emergence of distributed graph-computing (DGC) frameworks. In these frameworks, the partitioning strategy plays an important role since it drives the communication cost and the workload balance among computing nodes, thereby affecting system performance. However, existing solutions only partially exploit a key characteristic of natural graphs commonly found in the real-world: their highly skewed power-law degree distributions. In this paper, we propose High-Degree (are) Replicated First (HDRF), a novel streaming vertex-cut graph partitioning algorithm that effectively exploits skewed degree distributions by explicitly taking into account vertex degree in the placement decision. We analytically and experimentally evaluate HDRF on both synthetic and real-world graphs and show that it outperforms all existing algorithms in partitioning quality.