Stream Processing of Shortest Path Query in Dynamic Road Networks
Mengxuan Zhang, Lei Li, Wen Hua, Xiaofang Zhou · IEEE Transactions on Knowledge and Data Engineering · 2020
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. Besides, they can also work in a highly dynamic environment as no index is needed. 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 that 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:Zigzagthat considers the1-Nshared computation;Co-Clusteringthat considers the source and target's spatial locality; andSearch-Space-Awarethat further incorporates search space estimation. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering:R2Rthat finds a set of approximate shortest paths from one region to another with bounded error; andLocal Cachethat improves the existingGlobal Cachewith higher cache hit ratio. Finally, we design three efficient stream processing methods for intra-batch shared computation. The 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.