Path Recommendation for Road Networks
Open Access
- Author:
- Shahid, Talal Ahmed
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Master of Science
- Document Type:
- Master Thesis
- Date of Defense:
- April 10, 2009
- Committee Members:
- Wang Chien Lee, Thesis Advisor/Co-Advisor
Wang Chien Lee, Thesis Advisor/Co-Advisor - Keywords:
- Multicriteria paths
Road Networks
Path Search
K-shortest paths - Abstract:
- Finding paths (that can be driving directions, ight itineraries, etc.) from a source to a destination upon a spatial network is a common but non-trivial activity in our daily life. In this thesis, we focus on nding driving directions on a road network. With the availability of high-precision digital maps, on-line path search becomes very convenient like in the case of MapQuest, GoogleMap and Yahoo!Map; while Garmin and TomTom navigation systems provide on-road directions. By specifying a source and a destination, a user can promptly retrieve an optimal path usually in terms of travel distance from the existing services and products. However, for many applications, one single path is inadequate due to various application needs, security and privacy concerns, and system performance. In this thesis, we study the design and implementation of a path recommendation system that provides multiple paths based on k-mincost path search and skyline path search. A k-mincost path search returns k di erent paths whose costs are the minimum among all possibile paths between a given source and destination. A Skyline path search returns a set of non-dominated paths when multiple types of costs such as travel time, mileage, road toll etc are considered simultaneously. Here, a path P is said to be dominated by another P0 if P0 is smaller than P for at least one type of cost and P0 is not larger than P for all the other types of costs. However, both the k-mincost and the skyline path searches are not simple extensions of any existing shortest path search methods. To address the need of new solutions to these searches, we examine the challenges behind these searches and explore their properties, based on which, we propose ecient search algorithms, namely, Passage Counting Algorithm and Progressive Skyline Search Algorithm, for k-mincost path search and skyline path search, respectively. Both of our proposed algorithms signi cantly outperform existing related approaches demonstrated through our extensive simulations and our comprehensive analysis.