Abstract:
In this thesis, we introduce a novel safe route planning problem and develop an efficient solution to ensure the travelers’ safety on roads. Though few research attempts have been made in this regard, all of them assume that people share their sensitive travel experiences with a centralized entity for finding the safest routes, which is not ideal in practice for privacy reasons. As a result, existing systems cannot provide safest routes with high accuracy due to the lack of data related to travel experiences. Furthermore, existing works formulate the safe route planning query in ways that do not meet a traveler’s need for safe travel on roads. Our approach finds the safest routes within a user-specified distance threshold based on the personalized travel experience of the knowledgeable crowd without involving any centralized computation. We develop a privacy preserving model to quantify the travel experience of a user into personalized safety scores. Our algorithms for finding the safest route further enhance user privacy by minimizing the exposure of personalized safety scores with others. Specifically, we develop two efficient algorithms, direct and iterative, to evaluate the safest route queries. The direct and the iterative algorithms offer trade-offs among the computation overhead, communication cost and privacy. We run extensive experiments using three real datasets to show the effectiveness and efficiency of our approach. Our iterative algorithm finds the safest route with 50% less exposure of personalized safety scores compared to that of direct algorithm. On the other hand, the computation overhead and the communication overhead for the direct algorithm are lower compared to those of the iterative algorithm. Although the direct algorithm is faster than the iterative algorithm, both of our algorithms take less than a second to process a query. Our experiments also show that lack of data for privacy issues can reduce the answer quality significantly. Our safe route planning system ensures the quality of the safest routes by protecting the privacy of the travel experiences of the users.
