Trip planning queries with location privacy

Abstract

In recent years, privacy issues have become a major concern for the proliferation of locationbased services (LBSs) and researchers have focused on protecting user privacy for variant of location-based queries. In this thesis, we propose techniques to protect location privacy of users for trip planning (TP) queries, a novel type of query in spatial databases. A TP query enables a user to plan a trip with the minimum travel distance, where the trip starts from a source location, go through a sequence of points of interest (POIs) (e.g., restaurant, shopping center), and ends at a destination. Due to privacy concerns, users may not wish to disclose her exact location to the location-based service provider (LSP). In this thesis, we present the rst comprehensive solution for processing TP queries without disclosing a user's actual source and destination locations to the LSP. We propose algorithms to evaluate optimal TP query answer with respect to both inaccurate and imprecise locations of users. We develop a novel technique to re ne search space as an elliptical region using geometric properties, which is the key idea behind the e ciency of our algorithms. Our extensive experiments show that the proposed approaches evaluate TP queries in real time with a high level of location privacy.