Exploring Historical Location Data for Anonymity Preservation in Location-Based Services

Abstract

We present a new approach for if-anonymity protection in Location-Based Services (LBSs). Specifically, we depersonalize location information by ensuring that each location reported for LBSs is a cloaking area that contains K different footprints-historical locations of different mobile nodes. Therefore, the exact identity and location of the service requestor remain anonymous from LBS service providers. Existing techniques, on the other hand, compute the cloaking area using current locations of K neighboring hosts of the service requestor. Because of this difference, our approach significantly reduces the cloaking area, which in turn decreases query processing and communication overhead for returning query results to the requesting host. In addition, existing techniques also require frequent location updates from all nodes, regardless of whether or not these nodes are requesting LBSs. Most importantly, our approach is the first practical solution that provides K-anonymity trajectory protection needed to ensure anonymity when a mobile host requests LBSs continuously as it moves. Our solution depersonalizes a user's trajectory (a time-series of the user's locations) based on the historical trajectories of other users. We evaluate our techniques under various conditions using location data synthetically generated based on real road maps. The results show that our techniques can provide K-anonymity trajectory protection using a minimized cloaking area.