Monitoring minimum cost paths on road networks

Yuan Tian, Ken C.K. Lee, Wang Chien Lee

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations

Abstract

On a road network, the minimum cost path (or min-cost path for short) from a source location to a destination is a path with the smallest travel cost among all possible paths. Despite that min-cost path queries on static networks have been well studied, the problem of monitoring min-cost paths on a road network in presence of updates is not fully explored. In this paper, we present PathMon, an efficient system for monitoring min-cost paths in dynamic road networks. PathMon addresses two important issues of the min-cost path monitoring problem, namely, (i) path invalidation that identifies min-cost paths returned to path queries affected by network changes, and (ii) path update that replaces invalid paths with new ones for those affected path queries. For (i), we introduce the notion of query scope, based on which a query scope index (QSI) is developed to identify affected path queries. For (ii), we devise a partial path computation algorithm (PPCA) to quickly recompute the updated paths. Through a comprehensive performance evaluation by simulation, QSI and PPCA are demonstrated to be effective on the path invalidation and path update issues.

Original languageEnglish (US)
Title of host publication17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009
Pages217-226
Number of pages10
DOIs
StatePublished - 2009
Event17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009 - Seattle, WA, United States
Duration: Nov 4 2009Nov 6 2009

Publication series

NameGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

Other

Other17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009
Country/TerritoryUnited States
CitySeattle, WA
Period11/4/0911/6/09

All Science Journal Classification (ASJC) codes

  • Earth-Surface Processes
  • Computer Science Applications
  • Modeling and Simulation
  • Computer Graphics and Computer-Aided Design
  • Information Systems

Fingerprint

Dive into the research topics of 'Monitoring minimum cost paths on road networks'. Together they form a unique fingerprint.

Cite this