Abstract:

Moving object databases (MOD) have gained much interest in recent years due to the advances in mobile communica- tions and positioning technologies. Study of MOD can re- veal useful information (e.g., traffic patterns and congestion trends) that can be used in applications for the common ben- efit. In order to mine and/or analyze the data, MOD must be published, which can pose a threat to the location pri- vacy of a user. Indeed, based on prior knowledge of a user’s location at several time points, an attacker can potentially associate that user to a specific moving object (MOB) in the published database and learn her position information at other time points. In this paper, we study the problem of privacy-preserving publishing of moving object database. Unlike in microdata, we argue that in MOD, there does not exist a fixed set of quasi-identifier (QID) attributes for all the MOBs. Conse- quently the anonymization groups of MOBs (i.e., the sets of other MOBs within which to hide) may not be disjoint. Thus, there may exist MOBs that can be identified explicitly by combining different anonymization groups. We illustrate the pitfalls of simple adaptations of classical k-anonymity and develop a notion which we prove is robust against pri- vacy attacks. We propose two approaches, namely extreme- union and symmetric anonymization, to build anonymiza- tion groups that provably satisfy our proposed k-anonymity requirement, as well as yield low information loss. We ran an extensive set of experiments on large real-world and syn- thetic datasets of vehicular traffic. Our results demonstrate the effectiveness of our approach.