Path Problems in Geographic Information Systems
Masoud Taghinezhad Omran · 2014
Path problems are among the most widely studied problems in graph theory. Unlike in well-studied conventional static shortest path problems, the characteristics of underlying networks may change over time in many real-world applications. An efficient solution to the Shortest Path problem, should therefore take the dynamics of the underlying graph into consideration. In this thesis, we study a dynamic version of the Shortest Path Problem in which travel times on links of the underlying graph change over time, and present improved and easily implemented exact and approximation algorithms. With theoretical improvements in time-dependent shortest path computation and technical advancements in the provision of real-time traffic data, many travelers these days use and rely on navigation systems and time-dependent shortest path computation in their everyday lives. This may, however, compromise users' privacy since untrusted Location Based Services (LBS) are able to use inference attacks to gain access to sensitive information about users, such as their driving habits, health conditions they may have, their sexual orientation, or details about their lifestyle. In this dissertation, we propose a heuristic algorithm that protects the privacy of users who submit frequent location based queries to a Location Based Service. Although, shortest paths are preferred in most applications related to navigation and transportation, they can easily be inferred and regenerated, and should therefore be avoided in applications where user security is paramount. For example, a traveling VIP is more concerned about the security of her path rather than its length. We study the traveling VIP problem in which the goal is to randomly select a path from k candidate source-destination paths. When links are shared between many paths security is compromised and security guards may have to be placed on such links. The number of shared edges, then, should be minimized to reduce the costs associated with security guards who must be assigned to each shared link. We show that this problem is hard to approximate, and propose an approximation algorithm which has been experimentally evaluated on various networks.