iKSP: A Path Enumeration Index in Road Networks

Enumerating the top- $k$ simple shortest path (KSP) is a fundamental searching strategy for many path-related applications. However, the efficiency of current solutions is not acceptable, especially when the required $k$ is large, which becomes a bottleneck for many downstream tasks like Diversified KSP (DkSP) and Constrained Shortest Path. Besides, it seems infeasible to build a KSP index specifically when $k$ is unknown beforehand. To break through these barriers, in this paper, we first propose an index $\boldsymbol{i}$ KSP for top-k path enumeration. Then we dive into the path concatenation relationship, and propose novel pruning techniques to efficiently detect the loopful and repeated paths for KSP computation. Finally, the experiment on real-life road networks demonstrates the effectiveness and efficiency of our algorithm over the state-of-the-art, and the application in DkSP shows the practicality of our algorithm.