A Parallel Algorithm to Answer Shortest Distance on Dynamic Graph

被引：0
作者：
Han S. [1 ]
Zou L. [1 ]
机构：
[1] Institute of Computer Science and Technology of Peking University, Beijing
来源：
Beijing Daxue Xuebao (Ziran Kexue Ban)/Acta Scientiarum Naturalium Universitatis Pekinensis | 2020年 / 56卷 / 01期
关键词：
Bidirectional bidirectional breath-first search (BFS); Data-level parallelism; Delta graph; Dynamic graph; Shortest distance; SIMD; Thread-level parallelism;
D O I：
10.13209/j.0479-8023.2019.113
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
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. © 2020 Peking University.
引用
收藏
页码：112 / 122
页数：10
相关论文
共 15 条
  • [1] Bramandia R., Choi B., Ng W.K., Incremental mainte-nance of 2-hop labeling of large graphs, TKDE, 22, 5, pp. 682-698, (2010)
  • [2] Zhu A.D., Lin W., Wang S., Et al., Reachability queries on large dynamic graphs: a total order approach, pp. 1323-1334, (2014)
  • [3] Franciosa P.G., Frigioni D., Giaccio R., Semi-dynamic shortest paths and breadth-first search in digraphs, pp. 33-46, (1997)
  • [4] Frigioni D., Marchetti-Spaccamela A., Nanni U., Fully dynamic algorithms for maintaining shortest paths trees, Journal of Algorithms, 34, 2, pp. 251-281, (2000)
  • [5] Roditty L., Zwick U., A fully dynamic reachability algorithm for directed graphs with an almost linear update time, SIAM Journal on Computing, 45, 3, pp. 712-733, (2016)
  • [6] Han S., Zou L., Yu J.X., Speeding up set intersections in graph algorithms using SIMD instructions, pp. 1587-1602, (2018)
  • [7] Goldberg A.V., Point-to-point shortest path algorithms with preprocessing, pp. 88-102, (2007)
  • [8] Zhou J., Kenneth A.R., Implementing database operations using SIMD instructions, pp. 145-156, (2002)
  • [9] Willhalm T., Popovici N., Boshmaf Y., Et al., SIMD-scan: ultra fast in-memory table scan using on-chip vector processing units, pp. 385-394, (2009)
  • [10] Feng Z., Lo E., Kao B., Et al., Byteslice: pushing the envelop of main memory data processing with a new storage layout, pp. 31-46, (2015)
12