Batch Processing of Shortest Path Queries in Road Networks

Mengxuan Zhang, Lei Li, Wen Hua, Xiaofang Zhou

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

Abstract

Shortest path algorithm is a foundation to various location-based services (LBS) and has been extensively studied in the literature. However, server-side shortest path calculation faces a severe scalability issue when the business expands and a huge amount of requests are submitted to the server simultaneously. Although a straightforward solution widely-adopted in current industry is to deploy more processing resources, in this work, we aim to improve the efficiency algorithmically by answering queries in a batch and reusing shareable computations. In particular, we generalize the goal-directed A* algorithm to correctly solve the batch processing problem with localized destinations. We further propose two decomposition algorithms to deal with scenarios where the destinations are sparse. Extensive evaluations on a real-world road network verify the superiority of our algorithm compared with state-of-the-art methods.

Original languageEnglish
Title of host publicationDatabases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings
EditorsLijun Chang, Xin Cao, Junhao Gan
PublisherSpringer Verlag
Pages3-16
Number of pages14
ISBN (Print)9783030120788
DOIs
Publication statusPublished - 2019
Externally publishedYes
Event30th Australasian Database Conference, ADC 2019 - Sydney, Australia
Duration: 29 Jan 20191 Feb 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11393 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference30th Australasian Database Conference, ADC 2019
Country/TerritoryAustralia
CitySydney
Period29/01/191/02/19

Keywords

  • Batch process
  • Road network
  • Shortest path

ASJC Scopus subject areas

  • Information Systems

Fingerprint

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

Cite this