A k-Anonymity Model for Spatio-Temporal Data

The unprecedented growth in location-based services (LBS) take-up along with the continuously increasing storage capabilities of modern systems, and have facilitated the collection of information related to users activities in space and time. In itself this fact constitutes a serious hazard to the privacy of individuals. In this paper, we extend existing work in the preservation of historical k-anonymity, by (i) enabling each user to have numerous spatio-temporal movement patterns (a.k.a. LBQIDs) associated with his profile, (ii) adapting the generalization algorithm of k-anonymity to account for those multiple LBQIDs. (Hi) defining a set of novel spatial regions which behave as dynamically constructed mix-zones, and (iv) introducing an unlinking algorithm, applied when the generalization algorithm fails, which protects users by unlinking their future requests from previous ones. Moreover, as part of our contribution, we construct a data generator that allows for the composition of spatio-temporal datasets. Finally, we use these datasets to provide an extensive and thorough experimental evaluation of our approach.