Presentation
PeeK: A Prune-Centric Approach for K Shortest Path Computation
SessionGraph Algorithms in HPC
DescriptionThe ๐พ shortest path (KSP) algorithm, which finds the top ๐พ shortest simple paths from a given source to a target vertex, has a wide range of real-world applications. While the top ๐พ shortest simple paths offer invaluable insights, computing them is time-consuming. In this work, we observe existing works search ๐พ shortest paths from the original graph, while the top ๐พ shortest paths only cover a meager portion of the original graph. This paper devises PeeK. It first applies ๐พ upper bound pruning to prune the vertices and edges that will not appear in any of the ๐พ shortest paths. Second, PeeK adaptively compacts the graph that, not only removes the deleted vertices or edges but also efficiently computes the downstream task. We compare PeeK with five algorithms. For parallel computation with 32 threads, PeeK achieves 5.1x and 28.8x speedup over the state-of-the-art for ๐พ = 8, 128, respectively.
