Parallel implementation of bisector epsilon-approximation shortest path algorithm for concurrent queries.

摘要

One of the most important factors in a parallel implementation of the shortest path computation, is how to partition the original graph to achieve better efficiency. Multi-dimensional Fixed Partition scheme introduced by Nussbaum offers an efficient partitioning solution. As an extension, SWP (Steiner Weighted Partitioning) re-partitions a page according to the weight of the page. This weight roughly represents the computation load in that page. Using this SWP, we have implemented a parallel application for the bisector - beta-approximation scheme.; Also, we introduce the concurrent PSP (parallel shortest path) computation, which handles concurrent shortest path queries simultaneously and leads to a higher speedup. The experimental results show that the parallel implementations using SWP are efficient and effective. We also show that this concurrent parallelization can achieve higher speedup and efficiency than the batch-mode parallelization.