Path Problems in Geographic Information Systems
Public Deposited- Resource Type
- Creator
- Abstract
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.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2014 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2014
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
taghinezhadomran-pathproblemsingeographicinformationsystems.pdf | 2023-05-04 | Public | Download |