动态图上的最短路径距离并行算法

韩硕, 邹磊^?

北京大学计算机科学技术研究所, 北京 100080

收稿日期:2019-01-11修回日期:2019-03-27出版日期:2020-01-20

A Parallel Algorithm to Answer Shortest Distance on Dynamic Graph

HAN Shuo, ZOU Lei^?

Institute of Computer Science and Technology of Peking University, Beijing 100080

Received:2019-01-11Revised:2019-03-27Published:2020-01-20

PDF

(1188KB)

可视化

0

复制本文网址

1. 探讨2016版国际胰瘘研究小组定义和分级系统对胰腺术后患者胰瘘分级的影响.PDF(500KB)

-->

摘要/Abstract

摘要： 设计动态图上最短路径距离查询的并行计算框架。通过构建增量图的方法, 实现一个批次内的多个查询在不同数据图版本的多线程并发执行。对于每个查询, 使用双向宽度优先搜索算法来减少搜索空间, 并提出搜索过程中扩展方向的决策函数。利用BSR对数据图邻接表进行编码, 结合 SIMD指令和图顶点重标号算法, 进一步提升数据级并行度。在真实图数据集下的大量实验验证了所提方法的高效性。

引用本文

韩硕, 邹磊. 动态图上的最短路径距离并行算法[J]. 北京大学学报自然科学版, 2020, 56(1): 112-122.
HAN Shuo, ZOU Lei. A Parallel Algorithm to Answer Shortest Distance on Dynamic Graph[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2020, 56(1): 112-122.





PDF全文下载地址:

http://xbna.pku.edu.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=3441