Anonymizing moving objects: how to hide a MOB in a crowd?

ABSTRACT

Moving object databases (MOD) have gained much interest in recent years due to the advances in mobile communications and positioning technologies. Study of MOD can reveal useful information (e.g., traffic patterns and congestion trends) that can be used in applications for the common benefit. In order to mine and/or analyze the data, MOD must be published, which can pose a threat to the location privacy 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. Consequently 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 privacy attacks. We propose two approaches, namely extreme-union and symmetric anonymization, to build anonymization 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 synthetic datasets of vehicular traffic. Our results demonstrate the effectiveness of our approach.

REFERENCES

• 1: Abul, O., Bonchi, F., and Nanni, M. Never Walk Alone: Uncertainty for anonymity in moving objects databases. In Proc. of the 24th IEEE Int. Conf. on Data Engineering (ICDE'08).
• 2: Aggarwal, G., Feder, T., Kenthapadi, K., Motwani, R., Panigrahy, R., Thomas, D., and Zhu, A. Anonymizing tables. In Proc. of the 10th Int. Conf. on Database Theory (ICDT'05).
• 3: Roberto J. Bayardo , Rakesh Agrawal, Data Privacy through Optimal k-Anonymization, Proceedings of the 21st International Conference on Data Engineering, p.217-228, April 05-08, 2005 [doi>10.1109/ICDE.2005.42]
• 4: Bettini, C., Wang, X. S., and Jajodia, S. Protecting Privacy Against Location-Based Personal Identification. In Proc. of the Second VLDB Workshop on Secure Data Management (SDM'05).
• 5: Brinkhoff, T. Generating traffic data. IEEE Data Eng. Bull. 26, 2 (2003), 19--25.
• 6: Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991 [doi>10.1145/116873.116878]
• 7: Marco Gruteser , Dirk Grunwald, Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking, Proceedings of the 1st international conference on Mobile systems, applications and services, p.31-42, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1189037]
• 8: Hamilton, C. Compact Hilbert Indices. Tech. Rep. CS-2006-07, Dalhousie University, July 2006.
• 9: Hilbert, D. Über die stetige abbildung einer linie auf ein flächenstück. Math. Ann. 38 (1891), 459--460.
• 10: Kristen LeFevre , David J. DeWitt , Raghu Ramakrishnan, Mondrian Multidimensional K-Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.25, April 03-07, 2006 [doi>10.1109/ICDE.2006.101]
• 11: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 12: Adam Meyerson , Ryan Williams, On the complexity of optimal K-anonymity, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055591]
• 13: Mohamed F. Mokbel, Towards Privacy-Aware Location-Based Database Servers, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.93, April 03-07, 2006 [doi>10.1109/ICDEW.2006.152]
• 14: Mohamed F. Mokbel , Chi-Yin Chow , Walid G. Aref, The new Casper: query processing for location services without compromising privacy, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 15: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 16: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 17: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 18: Reza Akbarinia , Esther Pacitti , Patrick Valduriez, Best position algorithms for top-k queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 19: Pierangela Samarati , Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract), Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.188, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275508]
• 20: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 21: Manolis Terrovitis , Nikos Mamoulis, Privacy Preservation in the Publication of Trajectories, Proceedings of the The Ninth International Conference on Mobile Data Management, p.65-72, April 27-30, 2008 [doi>10.1109/MDM.2008.29]
• 22: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering, p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]