Stream Processing of Shortest Path Query in Dynamic Road Networks

Mengxuan Zhang, Lei Li, Wen Hua, Xiaofang Zhou

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

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: Zigzag that considers the 1-N shared computation; Co-Clustering that considers the source and target's spatial locality; and Search-Space-Aware that 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: R2R that finds a set of approximate shortest paths from one region to another with bounded error; and Local Cache that improves the existing Global Cache with 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.

Original languageEnglish
Pages (from-to)2458-2471
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number5
DOIs
Publication statusPublished - 1 May 2022
Externally publishedYes

Keywords

  • qurey decomposition
  • Shortest path query
  • stream processing

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Stream Processing of Shortest Path Query in Dynamic Road Networks'. Together they form a unique fingerprint.

Cite this