Advanced Path Queries in Road Networks

Open Access
- Author:
- Tian, Yuan
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Master of Science
- Document Type:
- Master Thesis
- Date of Defense:
- November 04, 2013
- Committee Members:
- Wang Chien Lee, Thesis Advisor/Co-Advisor
Sencun Zhu, Thesis Advisor/Co-Advisor
Raj Acharya, Thesis Advisor/Co-Advisor - Keywords:
- Road networks
path query
algorithm
location-based service - 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 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 identies min-cost paths returned to path queries aected by network changes, and (ii) path update that replaces invalid paths with new ones for those aected path queries. For (i), we introduce the notion of query scope, based on which a query scope index (QSI) is developed to identify aected 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 eective on the path invalidation and path update issues. The query processing performance of QSI and PPCA outperformed the compared algorithms.