Typical Snapshots Selection for Shortest Path Query in Dynamic 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

2 Citations (Scopus)

Abstract

Finding the shortest paths in road network is an important query in our life nowadays, and various index structures are constructed to speed up the query answering. However, these indexes can hardly work in real-life scenario because the traffic condition changes dynamically, which makes the pathfinding slower than in the static environment. In order to speed up path query answering in the dynamic road network, we propose a framework to support these indexes. Firstly, we view the dynamic graph as a series of static snapshots. After that, we propose two kinds of methods to select the typical snapshots. The first kind is time-based and it only considers the temporal information. The second category is the graph representation-based, which considers more insights: edge-based that captures the road continuity, and vertex-based that reflects the region traffic fluctuation. Finally, we propose the snapshot matching to find the most similar typical snapshot for the current traffic condition and use its index to answer the query directly. Extensive experiments on real-life road network and traffic conditions validate the effectiveness of our approach.

Original languageEnglish
Title of host publicationDatabases Theory and Applications - 31st Australasian Database Conference, ADC 2020, Proceedings
EditorsRenata Borovica-Gajic, Jianzhong Qi, Weiqing Wang
PublisherSpringer
Pages105-120
Number of pages16
ISBN (Print)9783030394684
DOIs
Publication statusPublished - 2020
Externally publishedYes
Event31st Australasian Database Conference, ADC 2019 - Melbourne, Australia
Duration: 3 Feb 20207 Feb 2020

Publication series

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

Conference

Conference31st Australasian Database Conference, ADC 2019
Country/TerritoryAustralia
CityMelbourne
Period3/02/207/02/20

Keywords

  • Dynamic road network
  • Shortest path
  • Snapshot selection

ASJC Scopus subject areas

  • Information Systems

Fingerprint

Dive into the research topics of 'Typical Snapshots Selection for Shortest Path Query in Dynamic Road Networks'. Together they form a unique fingerprint.

Cite this