Technical Papers Archive

PeeK: A Prune-Centric Approach for K Shortest Path Computation

Authors: Wang Feng (University of North Texas), Shiyang Chen and Hang Liu (Rutgers University), and Yuede Ji (University of North Texas)

Abstract: The 𝐾 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.




Back to Technical Papers Archive Listing