北京大学学报自然科学版 ›› 2020, Vol. 56 ›› Issue (1): 112-122.DOI: 10.13209/j.0479-8023.2019.113

上一篇    下一篇

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

韩硕, 邹磊†   

  1. 北京大学计算机科学技术研究所, 北京 100080
  • 收稿日期:2019-01-11 修回日期:2019-03-27 出版日期:2020-01-20 发布日期:2020-01-20
  • 通讯作者: 邹磊, E-mail: zoulei(at)pku.edu.cn

A Parallel Algorithm to Answer Shortest Distance on Dynamic Graph

HAN Shuo, ZOU Lei†   

  1. Institute of Computer Science and Technology of Peking University, Beijing 100080
  • Received:2019-01-11 Revised:2019-03-27 Online:2020-01-20 Published:2020-01-20
  • Contact: ZOU Lei, E-mail: zoulei(at)pku.edu.cn

PDF

摘要：

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

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

Abstract:

The paper presents a parallel algorithm framework to answer shortest distance queries on dynamic graphs. Based on maintaining a delta graph, multiple queries within a batch are executed in parallel over different versions of data graph by multi-threading. For each query, bidirectional breath-first search (BFS) is utilized to reduce search space. During the search process, an exploration direction decision-making function is proposed. Furthermore, adjacency-lists of data graph are encoded by BSR layout, combined with SIMD instructions and graph reordering algorithm, higher degree of data-level parallelism is achieved. Extensive experiments on real graph datasets confirm the superior efficiency of the proposed solution.

Key words: dynamic graph, shortest distance, delta graph, thread-level parallelism, data-level parallelism, bidirectional bidirectional breath-first search (BFS), SIMD

版权所有 © 《北京大学学报（自然科学版）》编辑部
技术支持：北京玛格泰克科技发展有限公司