GPU Accelerated Construction of Time Respecting Data Structure for Temporal Graphs

The transformation of a temporal graph into its corresponding time-respecting graph (TRG) offers significant advantages for neighborhood search problems when compared to the traditional edge stream representations. However, constructing TRGs is a time-consuming process that can be substantially accelerated using GPU based parallelism. In this paper, we propose a novel highly parallel method to construct the timerespecting graph (TRG) from the edge list by leveraging GPU parallelism. For graphs of various sizes, ranging from 0.05 to 33 million edges, we achieve a speedup of up to 387x over the sequential variant on comparable hardware. We demonstrate that our method produces TRG in the standard CSR form that can be input to high-performance graph analytics libraries such as nvGRAPH. The TRG produced is also optimized for a minimal number of vertices and edges. Our method also provides support for efficient real-time dynamic updates to the temporal graph.