A speedup technique for dynamic graphs using partitioning strategy and multithreaded approach

Abstract

There are many pre-processing-based speedup techniques for shortest path problems that are available in the literature. These techniques have an increased demand because of large datasets in such applications such as roadmaps, web search engines and mobile data sets. Pre-processing for the Time-Dependent Shortest Path Problem is still a demanding process that involves graph or network partitioning strategy. Efficient pre-processing of graphs or networks reduces the shortest path computation time while parallelizing the pre-processing phase improves the speedup of the system. In this paper, a speedup technique called Recursive Spectral Bisection (RSB) combined with the Elliptic Convolution of the shortest path method is proposed for dynamic Time-Dependent networks. The same method has been parallelized, and the results are tested on three types of graphs. It is observed that the Time-Dependent RSB combined with the Elliptic Convolution of the shortest path method has no update time, and the Query Performance Loss (QPL) is reduced in planar and road networks compared to random networks. In road networks, the proposed method achieves an average speedup in a QPL of 140. The use of the Parallel speedup technique results in an average speedup in a QPL of more than 1 in the planar and road networks.

Keywords

• Dijkstra’s algorithm
• Speedup techniques
• Dynamic graphs
• Parallel programming