Advanced Path Queries in Road Networks

Open Access
Tian, Yuan
Graduate Program:
Computer Science and Engineering
Master of Science
Document Type:
Master Thesis
Date of Defense:
November 04, 2013
Committee Members:
  • Wang Chien Lee, Thesis Advisor
  • Sencun Zhu, Thesis Advisor
  • Raj Acharya, Thesis Advisor
  • Road networks
  • path query
  • algorithm
  • location-based service
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 thesis, we present PathMon, an ecient 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 identi es min-cost paths returned to path queries a ected by network changes, and (ii) path update that replaces invalid paths with new ones for those a ected path queries. For (i), we introduce the notion of query scope, based on which a query scope index (QSI) is developed to identify a ected path queries. For (ii), we devise a partial path computation algorithm (PPCA) to quickly recompute the updated paths. We have conducted a comprehensive performance evaluation by simulation, on various road networks and simulation settings. In these evaluations, we demonstrate that the proposed techniques, QSI and PPCA, are very e ective on the path invalidation and path update issues. The query processing performance of QSI and PPCA outperformed the compared algorithms.