• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Group Reassignment for Dynamic Edge Partitioning
【24h】

Group Reassignment for Dynamic Edge Partitioning

机译：组重新分配动态边缘分区

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Graph partitioning is a mandatory step in large-scale distributed graph processing. When partitioning real-world power-law graphs, the edge partitioning algorithm performs better than the traditional vertex partitioning algorithm, because it can cut a single vertex into multiple replicas to apportion the computation. Many advanced edge partitioning methods are designed for partitioning a static graph from scratch. However, the real-world graph structure changes continuously, which leads to a decrease in partition quality and affects the performance of the graph applications. Some studies are devoted to offline repartitioning or batch incremental partitioning, but how to deal with dynamics in real-time is still worthy of in-depth study. In this article, we discuss the impact of dynamic change on partition and discover that both insertion and deletion will lead to local suboptimal partitioning, which is the reason for the degradation of partition quality. As a solution, a dynamic edge partitioning algorithm is proposed to partition dynamics in real-time. Specifically, we deal with dynamics by a distributed stream and improve partition quality by reassigning some closely connected edges. Experiments show that it is robust to initial partition quality, dynamic scale and type, and distributed scale. Compared with the state-of-the-art dynamic partitioner, it can reduce vertex-cuts by 29.5 percent. Compared with the repartitioning algorithms, it can save the partitioning time by 91.0 percent. Applied on the graph task, it can reduce the increase of communication cost and the increase of the total time of task by 41.5 and 71.4 percent.
机译：图形分区是大规模分布式图处理的强制性步骤。当划分现实世界权力法图时，边缘划分算法比传统的顶点分区算法更好，因为它可以将单个顶点切割成多个副本以分配计算。许多高级边缘分区方法旨在从头开始划分静态图。但是，实际世界图形结构连续变化，这导致分区质量的降低，并影响图形应用的性能。一些研究致力于离线重新分区或批量增量分区，但如何实时处理动态仍然值得深入研究。在本文中，我们讨论了动态变化对分区的影响，并发现插入和删除都会导致本地次优分区，这是分区质量劣化的原因。作为解决方案，建议实时分区动态的动态边缘分区算法。具体而言，我们通过分布式流处理动态，并通过重新分配一些紧密连接的边缘来提高分区质量。实验表明，它是初始分区质量，动态比例和类型和分布式规模的强大。与最先进的动态分区相比，它可以减少29.5％的顶点切割。与重新分区算法相比，它可以将分区时间保存为91.0％。应用于图表任务，它可以降低通信成本的增加，并将任务总时间增加41.5％和71.4％。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号