  The problem of identifying the k-shortest paths (KSPs for short) in a dynamic
road network is essential to many location-based services. Road networks are
dynamic in the sense that the weights of the edges in the corresponding graph
constantly change over time, representing evolving traffic conditions. Very
often such services have to process numerous KSP queries over large road
networks at the same time, thus there is a pressing need to identify
distributed solutions for this problem. However, most existing approaches are
designed to identify KSPs on a static graph in a sequential manner (i.e., the
(i+1)-th shortest path is generated based on the i-th shortest path),
restricting their scalability and applicability in a distributed setting. We
therefore propose KSP-DG, a distributed algorithm for identifying k-shortest
paths in a dynamic graph. It is based on partitioning the entire graph into
smaller subgraphs, and reduces the problem of determining KSPs into the
computation of partial KSPs in relevant subgraphs, which can execute in
parallel on a cluster of servers. A distributed two-level index called DTLP is
developed to facilitate the efficient identification of relevant subgraphs. A
salient feature of DTLP is that it indexes a set of virtual paths that are
insensitive to varying traffic conditions, leading to very low maintenance cost
in dynamic road networks. This is the first treatment of the problem of
processing KSP queries over dynamic road networks. Extensive experiments
conducted on real road networks confirm the superiority of our proposal over
baseline methods.
