Single-Source Shortest Path Tree for Big Dynamic Graphs
Single-Source Shortest Path Tree for Big Dynamic Graphs
复制标题
大动态图的单源最短路径树
DOI：
10.1109/bigdata.2018.8622042
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Norris, Boyana
中科院分区：
文献类型：
--
作者：
Riazi, Sara;Srinivasan, Sriram;Das, Sajal K.;Bhowmick, Sanjukta;Norris, Boyana
计算单源最短路径（SSSP）是图论中的基本问题之一。 SSSP 有许多应用，包括在 GPS 系统中查找路线以及查找有效疫苗接种的高中心性顶点。在本文中，我们重点计算随时间变化的大动态图上的 SSSP。我们提出了一种新颖的分布式计算方法 SSSPIncJoint，用于使用 GraphX 更新大型动态图上的 SSSP。我们的方法通过减少在 GraphX 使用的收集-应用-分散编程模型中实现 SSSP 所需的映射-归约操作数量，显着加快了 SSSP 树的重新计算速度。
Computing single-source shortest paths (SSSP) is one of the fundamental problems in graph theory. There are many applications of SSSP including finding routes in GPS systems and finding high centrality vertices for effective vaccination. In this paper, we focus on calculating SSSP on big dynamic graphs, which change with time. We propose a novel distributed computing approach, SSSPIncJoint, to update SSSP on big dynamic graphs using GraphX. Our approach considerably speeds up the recomputation of the SSSP tree by reducing the number of map-reduce operations required for implementing SSSP in the gather-apply- scatter programming model used by GraphX.
大型动态网络中单源最短路径更新的共享内存并行算法
DOI：
10.1109/hipc.2018.00035
发表时间：
2018
期刊：
2018 IEEE 25th International Conference on High Performance Computing (HiPC
影响因子：
--
作者：
Srinivasan, Sriram;Riazi, Sara;Norris, Boyana;Das, Sajal K.;Bhowmick, Sanjukta
通讯作者：
Bhowmick, Sanjukta
在 GPU 上使用 JavaScript 的动态最短路径
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
A. Ingole
通讯作者：
A. Ingole