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

作     者：韩硕 邹磊 HAN Shuo;ZOU Lei

作者机构：北京大学计算机科学技术研究所 

出 版 物：《北京大学学报（自然科学版）》 (Acta Scientiarum Naturalium Universitatis Pekinensis)

年 卷 期：2020年第56卷第1期

页      码：112-122页

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

主 题 词：动态图 最短路径距离 增量图 线程级并行 数据级并行 双向宽度优先搜索 SIMD 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13209/j.0479-8023.2019.113

馆 藏 号：203884241...