TY - GEN
T1 - Monitoring minimum cost paths on road networks
AU - Tian, Yuan
AU - Lee, Ken C.K.
AU - Lee, Wang Chien
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=74049123161&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=74049123161&partnerID=8YFLogxK
U2 - 10.1145/1653771.1653803
DO - 10.1145/1653771.1653803
M3 - Conference contribution
AN - SCOPUS:74049123161
SN - 9781605586496
T3 - GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
SP - 217
EP - 226
BT - 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009
T2 - 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2009
Y2 - 4 November 2009 through 6 November 2009
ER -