Path Query Processing Using Typical Snapshots in Dynamic Road Networks

Mengxuan Zhang, Lei Li, Pingfu Chao, Wen Hua, Xiaofang Zhou

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

3 Citations (Scopus)

Abstract

The shortest path query in road network is a fundamental operation in navigation and location-based services. The existing shortest path algorithms aim at improving efficiency in the static/time-dependent environment. However, the real-life road networks are dynamic, so they can hardly meet the requirement in practice. In this paper, we aim to support the path query in dynamic road networks by identifying the typical snapshots from the snapshot sequences, building the path indexes on them, and finally processing the query with the most suitable typical snapshot. Specifically, we first use the typical OD pairs to capture the dynamic information and represent the snapshots. Then the snapshot similarity is measured by considering the shortest path error and the shortest path similarity of these OD pairs. Because the OD pair number is huge and they have different power in capturing the traffic condition, we further propose a hot region-based OD selection method that could select a small but powerful OD set. Lastly, we use the distance-based-quantile error for the query accuracy evaluation and conduct experiments in a large real-world dynamic road network to verify the effectiveness of our method compared with the state-of-the-art.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 25th International Conference, DASFAA 2020, Proceedings
EditorsYunmook Nah, Bin Cui, Sang-Won Lee, Jeffrey Xu Yu, Yang-Sae Moon, Steven Euijong Whang
PublisherSpringer Science and Business Media Deutschland GmbH
Pages255-271
Number of pages17
ISBN (Print)9783030594183
DOIs
Publication statusPublished - 2020
Externally publishedYes
Event25th International Conference on Database Systems for Advanced Applications, DASFAA 2020 - Jeju, Korea, Republic of
Duration: 24 Sept 202027 Sept 2020

Publication series

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

Conference

Conference25th International Conference on Database Systems for Advanced Applications, DASFAA 2020
Country/TerritoryKorea, Republic of
CityJeju
Period24/09/2027/09/20

Keywords

  • Dynamic road network
  • Shortest path
  • Typical snapshot

ASJC Scopus subject areas

  • Information Systems

Fingerprint

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

Cite this