Solving All-Pairs Shortest-Paths Problem in Large Graphs Using Apache Spark
Solving All-Pairs Shortest-Paths Problem in Large Graphs Using Apache Spark
复制标题
使用 Apache Spark 解决大型图中的全对最短路径问题
DOI：
10.1145/3337821.3337852
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zola, Jaroslaw
中科院分区：
文献类型：
--
作者：
Schoeneman, Frank;Zola, Jaroslaw
计算全对最短路径 (APSP) 的算法是许多实际应用的关键构建块。标准的顺序算法，例如 Floyd-Warshall 和 Johnson，很快就变得不适用于大型输入图，需要并行方法。在这项工作中，我们使用 Apache Spark 提出、实现并彻底分析了分布式内存集群上 APSP 的不同策略。我们的求解器专为大型无向加权图而设计，其复杂性和对纯 Spark API 之外的技术的依赖程度有所不同。我们证明，性能最佳的求解器能够处理 1024 核集群上超过 200,000 个顶点的 APSP 问题。然而，它需要辅助共享持久存储来弥补 Spark 功能的缺失。
Algorithms for computing All-Pairs Shortest-Paths (APSP) are critical building blocks underlying many practical applications. The standard sequential algorithms, such as Floyd-Warshall and Johnson, quickly become infeasible for large input graphs, necessitating parallel approaches. In this work, we propose, implement and thoroughly analyse different strategies for APSP on distributed memory clusters with Apache Spark. Our solvers are designed for large undirected weighted graphs, and differ in complexity and degree of reliance on techniques outside of pure Spark API. We demonstrate that the best performing solver is able to handle APSP problems with over 200,000 vertices on a 1024-core cluster. However, it requires auxiliary shared persistent storage to compensate for missing Spark functionality.
DOI：
10.1109/hpec.2016.7761646
发表时间：
2016-06
期刊：
2016 IEEE High Performance Extreme Computing Conference (HPEC)
影响因子：
--
作者：
J. Kepner;Peter Aaltonen;David A. Bader;A. Buluç;F. Franchetti;J. Gilbert;D. Hutchison;Manoj Kumar;A. Lumsdaine;Henning Meyerhenke;Scott McMillan;Carl Yang;John Douglas Owens;Marcin Zalewski;T. Mattson;J. Moreira
通讯作者：
J. Kepner;Peter Aaltonen;David A. Bader;A. Buluç;F. Franchetti;J. Gilbert;D. Hutchison;Manoj Kumar;A. Lumsdaine;Henning Meyerhenke;Scott McMillan;Carl Yang;John Douglas Owens;Marcin Zalewski;T. Mattson;J. Moreira
DOI：
10.1136/ebmh.11.4.102
发表时间：
2008-10
期刊：
Evidence Based Mental Health
影响因子：
--
作者：
P. Cochat;L. Vaucoret;J. Sarles
通讯作者：
P. Cochat;L. Vaucoret;J. Sarles