skip to main content
10.1145/1503402.1503413acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
research-article

Towards trajectory anonymization: a generalization-based approach

Published: 04 November 2008 Publication History

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]
G. Agrawal, T. Feder, K. Kenthapadi, S. Khuller, R. Panigrahy, D. Thomas, and A. Zhu. Achieving anonymity via clustering. In PODS '06: Proc. of the 25th ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 153--162, Chicago, IL, USA, June 26-28 2006.
[3]
V. S. V. Aris Gkoulalas-Divanis. A free terrain model for trajectory k-anonymity. In 19th International Conference on Database and Expert Systems Applications - DEXA '08, pages 49--56, 2008.
[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]
J. Domingo-Ferrer and V. Torra. Ordinal, continuous and heterogeneous k-anonymity through microaggregation. Data Min. Knowl. Discov., 11(2):195--212, 2005.
[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]
B. Gedik and L. Liu. Location privacy in mobile systems: A personalized anonymization model. In The 25th International Conference on Distributed Computing Systems (ICDCS'05), 2005.
[17]
G. Ghinita, P. Kalnis, A. Khoshgozaran, C. Shahabi, and K.-L. Tan. Private queries in location based services: anonymizers are not necessary. In SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 121--132, New York, NY, USA, 2008. ACM.
[18]
M. Gruteser and D. Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In Proceedings of the 1st International Conference on Mobile Systems, Applications, and Services, 2003.
[19]
M. Gruteser and X. Liu. Protecting privacy in continuous location-tracking applications. IEEE Security and Privacy, 02(2):28--34, 2004.
[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]
B. Hoh and M. Gruteser. Protecting location privacy through path confusion. In SECURECOMM '05: Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks (SECURECOMM'05), pages 194--205, Washington, DC, USA, 2005. IEEE Computer Society.
[23]
B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Preserving privacy in gps traces via density-aware path cloaking. In ACM Conference on Computer and Communications Security (CCS), VA, USA, Oct. 29 2007.
[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]
K. LeFevre, D. J. DeWitt, and R. Ramakrishnan. Mondrian multidimensional k-anonymity. In Proceedings of the 22nd International Conference on Data Engineering (ICDE '06), pages 25--35, Atlanta, GA, Apr. 3-7 2006.
[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]
A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. In Proc. of the 22nd IEEE Int'l Conf. on Data Engineering (ICDE 2006), Atlanta Georgia, Apr. 2006.
[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]
M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new casper: query processing for location services without compromising privacy. In VLDB '06: Proceedings of the 32nd international conference on Very large data bases, pages 763--774. VLDB Endowment, 2006.
[33]
M. E. Nergiz, M. Atzori, and C. Clifton. Hiding the presence of individuals in shared databases. In SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data, Beijing, China, June 11-14 2007.
[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. E. Nergiz and C. Clifton. Thoughts on k-anonymization. Data and Knowledge Engineering, 63(3):622--645, Dec. 2007.
[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, 13(6):1010--1027, 2001.
[39]
L. Sweeney. k-anonymity: a model for protecting privacy. Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 10(5):557--570, 2002.
[40]
M. Terrovitis and N. Mamoulis. Privacy preservation in the publication of trajectories. Mobile Data Management, 2008. MDM '08. 9th International Conference on, pages 65--72, April 2008.
[41]
T. M. Truta and A. Campan. k-anonymization incremental maintenance and optimization techniques. In ACM Symposium on Applied Computing (SAC2007), page 380 -- 387, Seoul, Korea, 2007.
[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]
R. C.-W. Wong, A. W.-C. Fu, K. Wang, and J. Pei. Minimality attack in privacy preserving data publishing. In VLDB '07: Proceedings of the 33rd international conference on Very large data bases, pages 543--554. VLDB Endowment, 2007.

Cited By

View all
  • (2024)A Privacy-Aware Remapping Mechanism for Location DataProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3636050(1433-1440)Online publication date: 8-Apr-2024
  • (2024)Trajectory Privacy Protection Method Based on Differential Privacy in CrowdsensingIEEE Transactions on Services Computing10.1109/TSC.2024.3455104(1-16)Online publication date: 2024
  • (2024)Challenges of spatio-temporal trajectory datasetsJournal of Location Based Services10.1080/17489725.2024.2371311(1-32)Online publication date: 27-Jun-2024
  • Show More Cited By

Index Terms

  1. Towards trajectory anonymization: a generalization-based approach

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      SPRINGL '08: Proceedings of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS
      November 2008
      94 pages
      ISBN:9781605583242
      DOI:10.1145/1503402
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 04 November 2008

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. k-anonymity
      2. privacy
      3. spatio temporal

      Qualifiers

      • Research-article

      Funding Sources

      Conference

      SPRINGL 08
      Sponsor:

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)44
      • Downloads (Last 6 weeks)6
      Reflects downloads up to 07 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)A Privacy-Aware Remapping Mechanism for Location DataProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3636050(1433-1440)Online publication date: 8-Apr-2024
      • (2024)Trajectory Privacy Protection Method Based on Differential Privacy in CrowdsensingIEEE Transactions on Services Computing10.1109/TSC.2024.3455104(1-16)Online publication date: 2024
      • (2024)Challenges of spatio-temporal trajectory datasetsJournal of Location Based Services10.1080/17489725.2024.2371311(1-32)Online publication date: 27-Jun-2024
      • (2024)Semi-local Time sensitive Anonymization of Clinical DataScientific Data10.1038/s41597-024-04192-111:1Online publication date: 20-Dec-2024
      • (2024)A three-way trajectory privacy-preserving model based on multi-feature fusionApplied Soft Computing10.1016/j.asoc.2024.111591(111591)Online publication date: Apr-2024
      • (2023)Privacy-Preserving Method for Trajectory Data Publication Based on Local Preferential AnonymityInformation10.3390/info1403015714:3(157)Online publication date: 2-Mar-2023
      • (2023)Traceable high-dimensional data publishing based on Alliance ChainProceedings of the 2023 5th International Conference on Blockchain Technology10.1145/3638025.3638027(1-7)Online publication date: 10-Nov-2023
      • (2023)Challenges of Spatio-Temporal Trajectory Data Use: Focus Group Findings from the 1st International Summer School on Data Science for MobilityProceedings of the 27th International Database Engineered Applications Symposium10.1145/3589462.3589478(51-58)Online publication date: 5-May-2023
      • (2023)Preserving Location Privacy in the Modern Era of Pervasive Environments2023 5th IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA)10.1109/TPS-ISA58951.2023.00015(44-51)Online publication date: 1-Nov-2023
      • (2023)CATS: Conditional Adversarial Trajectory Synthesis for privacy-preserving trajectory data publication using deep learning approachesInternational Journal of Geographical Information Science10.1080/13658816.2023.226255037:12(2538-2574)Online publication date: 9-Oct-2023
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media