Stream Processing of Shortest Path Query in Dynamic Road Networks

Shortest path query in road network is pervasive in various location-based services nowadays. As the business expands, the scalability issue becomes severer and more servers are deployed to cope with it. Moreover, as the traffic condition keeps changing over time, the existing index-based approaches can hardly adapt to the real-life dynamic environment. Therefore, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this work, we assume the traffic condition is stable over a short period and treat the issued queries within this period as a stream of query sets. Specifically, we first propose three query set decomposition methods to cluster one query set into multiple query subsets. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering. Finally, we design three efficient stream processing methods for intra-batch shared computation. Experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.