.png){kind=icon}
返回
GoGraph: Accelerating Graph Processing Through Incremental Reordering
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2025.3623928.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
大量图分析算法涉及迭代计算，这些计算占据了运行时间的主要部分。加速迭代图计算已成为提高图算法性能的关键。尽管已有大量研究专注于通过减少每次迭代的运行时间来提升效率，但迭代次数的优化往往被忽视。在本文中，我们首先建立了顶点处理顺序与迭代次数之间的关联，为减少迭代次数提供了可能性。我们提出一个度量函数来评估顶点处理顺序在加速迭代计算方面的有效性。利用该度量函数，我们提出了一种新颖的图重排方法GoGraph，该方法构建高效的顶点处理顺序。此外，针对演化图，我们进一步提出一个度量函数，用于评估顶点处理顺序对图变化的响应效果，并提供了三种用于动态调整顶点处理顺序的可选方法。我们的实验结果表明，GoGraph超越了当前最先进的重排算法，平均将运行时间提升了1.83倍（最高达3.34倍）。与传统的同步计算方法相比，我们的方法将迭代计算速度提升了最高4.46倍。在动态场景中，增量式GoGraph可将端到端时间平均减少43%（最高达48%）。
Keyword:
Graph reorder
iterative computation
asynchronous model
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容