Advanced Path Queries in Road Networks
Open Access
- 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
- Sencun Zhu, Thesis Advisor
- Raj Acharya, Thesis 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 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.