Continuously monitoring alternative shortest paths on road networks

Lingxiao Li, Muhammad Aamir Cheema, Mohammed Eunus Ali, Hua Lu, David Taniar

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


Modern navigation systems do not only provide shortest paths but also some alternative paths to provide more options to the users. This paper is the first to study the problem of continuously reporting alternative paths for a user traveling along a given path. Specifically, given a path P on which a user is traveling, we continuously report to the user k paths from the user's current location on P to the target t. We present several algorithms each improving on the previous based on non-trivial observations and novel optimisations. The proposed algorithms maintain and exploit the previously computed useful information to efficiently update the k alternative paths as the user moves. We provide space and time complexity analysis for each proposed algorithm. We conduct a comprehensive experimental study on large real-world road networks. The results demonstrate that the proposed algorithms are up to several orders of magnitude faster than the straightforward algorithms.

Original languageEnglish
Title of host publicationProceedings of the VLDB Endowment
EditorsMagdalena Balazinska, Xiaofang Zhou
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages13
Publication statusPublished - 2020
EventInternational Conference on Very Large Databases 2020 - Tokyo, Japan
Duration: 31 Aug 20204 Sep 2020
Conference number: 46th (Proceedings) (Website)

Publication series

NameProceedings of the VLDB Endowment
PublisherVLDB Endowment
ISSN (Electronic)2150-8097


OtherInternational Conference on Very Large Databases 2020
Abbreviated titleVLDB 2020
Internet address

Cite this