Towards trajectory anonymization: a generalization-based approach

ABSTRACT

Trajectory datasets are becoming more and more popular due to the massive usage of GPS and other location-based devices and services. In this paper, we address privacy issues regarding the identification of individuals in static trajectory datasets. We provide privacy protection by definig trajectory k-anonymity, meaning every released information refers to at least k users/trajectories. We propose a novel generalization-based approach that applies to trajectories and sequences in general. We also suggest the use of a simple random reconstruction of the original dataset from the anonymization, to overcome possible drawbacks of generalization approaches.

We present a utility metric that maximizes the probability of a good representation and propose trajectory anonymization techniques to address time and space sensitive applications. The experimental results over synthetic trajectory datasets show the effectiveness of the proposed approach.

REFERENCES

• 1: C. C. Aggarwal and P. S. Yu. A condensation approach to privacy preserving data mining. In EDBT'04, pages 183--199, Heraklion, Crete, Greece, Mar. 14 2004.
• 2: Gagan Aggarwal , Tomás Feder , Krishnaram Kenthapadi , Samir Khuller , Rina Panigrahy , Dilys Thomas , An Zhu, Achieving anonymity via clustering, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142374]
• 3: Aris Gkoulalas-Divanis , Vassilios S. Verykios, A Free Terrain Model for Trajectory K---Anonymity, Proceedings of the 19th international conference on Database and Expert Systems Applications, September 01-05, 2008, Turin, Italy [doi>10.1007/978-3-540-85654-2_6]
• 4: M. Atzori. Weak -anonymity: A low-distortion model for protecting privacy. In ISC, pages 60--71, 2006.
• 5: C. Bettini, X. S. Wang, and S. Jajodia. Protecting privacy against location-based personal identification. In Secure Data Management, pages 185--199, 2005.
• 6: F. Bonchi, O. Abul, and M. Nanni. Never walk alone: Uncertainty for anonymity in moving objects databases. In Proceedings of the 24nd International Conference on Data Engineering (ICDE '08), Cancun, Mexico, Apr. 7 2008.
• 7: J.-W. Byun, A. Kamra, E. Bertino, and N. Li. Efficient k-anonymization using clustering techniques. In (DASFAAŠ07), Apr. 2007.
• 8: J.-W. Byun, Y. Sohn, E. Bertino, and N. Li. Secure anonymization for incremental datasets. In Third VLDB Workshop on Secure Data Management (SDM'06), Seoul, Korea, Sept. 18 2006.
• 9: L. Chen and R. Ng. The marriage of lp-norms and edit distance, 2004.
• 10: R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar. Preserving user location privacy in mobile data management infrastructures. In 6th Workshop Privacy Enhancing Technology Workshop, pages 393--412. Springer, 2006.
• 11: M. Diomo and S. Ayman. Potential use of gps data for calibrating travel demand models. In 10th National Conference on Transportation Planning for Small and Medium-Sized Communities, Nashville Tennessee, USA, Sept. 13-15 2006.
• 12: Josep Domingo-Ferrer , Vicenç Torra, Ordinal, Continuous and Heterogeneous k-Anonymity Through Microaggregation, Data Mining and Knowledge Discovery, v.11 n.2, p.195-212, September 2005 [doi>10.1007/s10618-005-0007-5]
• 13: M. Duckham and L. Kulik. A formal model of obfuscation and negotiation for location privacy. In Pervasive, pages 152--170, 2005.
• 14: European Parliament. Directive 95/46/ec. http://www.cdt.org/privacy/eudirective/EU_Directive_.html, 1995.
• 15: European Parliament. Regulation (ec) no 45/2001. http://ec.europa.eu/justice_home/fsj/privacy/docs/application/286_en.pdf, Dec. 18 2000.
• 16: Bugra Gedik , Ling Liu, Location Privacy in Mobile Systems: A Personalized Anonymization Model, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.620-629, June 06-10, 2005 [doi>10.1109/ICDCS.2005.48]
• 17: Gabriel Ghinita , Panos Kalnis , Ali Khoshgozaran , Cyrus Shahabi , Kian-Lee Tan, Private queries in location based services: anonymizers are not necessary, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376631]
• 18: 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]
• 19: Marco Gruteser , Xuan Liu, Protecting Privacy in Continuous Location-Tracking Applications, IEEE Security and Privacy, v.2 n.2, p.28-34, March 2004 [doi>10.1109/MSECP.2004.1281242]
• 20: D. Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds. In Bull. Math. Biol., pages 141--154, 1993.
• 21: The health insurance portability and accountability act of 1996. Technical Report Federal Register 65 FR 82462, Department of Health and Human Services, Office of the Secretary, Dec. 2000.
• 22: Baik Hoh , Marco Gruteser, Protecting Location Privacy Through Path Confusion, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.194-205, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.33]
• 23: Baik Hoh , Marco Gruteser , Hui Xiong , Ansaf Alrabady, Preserving privacy in gps traces via uncertainty-aware path cloaking, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315266]
• 24: A. O. hrn and L. Ohno-Machado. Using boolean reasoning to anonymize databases. Artificial Intelligence in Medicine, 15(3):235--254, Mar. 1999.
• 25: T. Jiang and L. Wang. On the complexity of multiple sequence alignment. J. Computer Biologyy, 1:337--348, 1994.
• 26: 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]
• 27: N. Li and T. Li. t-closeness: Privacy beyond k-anonymity and l-diversity. In Proceedings of the 23nd International Conference on Data Engineering (ICDE '07), Istanbul, Turkey, Apr. 16-20 2007.
• 28: D. Luper, D. Cameron, J. A. Miller, and H. R. Arabnia. Spatial and temporal target association through semantic analysis and gps data mining. In The 2007 World Congress in Computer Science, Computer Engineering, & Applied Computing (IKE'07), Las Vegas, USA, June 25-28 2007.
• 29: 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]
• 30: T. McGhee. Gps technology tracks employees. http://www.denverpost.com/headlines/ci_4800440, 2006.
• 31: MIT SENSEable City Lab. Real time rome. http://senseable.mit.edu/realtimerome/, 2006.
• 32: 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
• 33: Mehmet Ercan Nergiz , Maurizio Atzori , Chris Clifton, Hiding the presence of individuals from shared databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247554]
• 34: M. E. Nergiz, M. Atzori, and C. Clifton. Towards trajectory anonymization: a generalization-based approach. Technical Report TR-08-015, Purdue University, 2008.
• 35: M. Ercan Nergiz , Chris Clifton, Thoughts on k-anonymization, Data & Knowledge Engineering, v.63 n.3, p.622-645, December, 2007 [doi>10.1016/j.datak.2007.03.009]
• 36: M. E. Nergiz, C. Clifton, and A. E. Nergiz. Multirelational k-anonymity. In Proceedings of the 23nd International Conference on Data Engineering (ICDE '07), Istanbul, Turkey, Apr. 16-20 2007.
• 37: Norwich Union. Pay as you drive. http://www.norwichunion.com/pay-as-you-drive/, 2007.
• 38: P. Samarati, Protecting Respondents' Identities in Microdata Release, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.1010-1027, November 2001 [doi>10.1109/69.971193]
• 39: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 40: 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]
• 41: Traian Marius Truta , Alina Campan, K-anonymization incremental maintenance and optimization techniques, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244093]
• 42: US Department of Transportation. Measuring day-to-day variability in travel behavior using gps data. http://www.fhwa.dot.gov/ohim/gps/conclusion.html, 2006.
• 43: Raymond Chi-Wing Wong , Ada Wai-Chee Fu , Ke Wang , Jian Pei, Minimality attack in privacy preserving data publishing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues

General Terms:
Algorithms, Legal Aspects, Security

Keywords:
k-anonymity, privacy, spatio temporal