Presentation

· Contributors · Organizations · Search Program · My Schedule · Happening Now · Maps

This content is available for: Tech Program Reg Pass. Upgrade Registration

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

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.

Authors