More Web Proxy on the site http://driver.im/

article

Towards Trajectory Anonymization: a Generalization-Based Approach

Authors:

Mehmet Ercan Nergiz,

Maurizio Atzori,

Yücel Saygın,

Barıʂ GüçAuthors Info & Claims

Transactions on Data Privacy, Volume 2, Issue 1

Pages 47 - 75

Published: 01 April 2009 Publication History

Abstract

Trajectory datasets are becoming popular due to the massive usage of GPS and location-based services. In this paper, we address privacy issues regarding the identification of individuals in static trajectory datasets. We first adopt the notion of k-anonymity to trajectories and propose a novel generalization-based approach for anonymization of trajectories. We further show that releasing anonymized trajectories may still have some privacy leaks. Therefore we propose a randomization based reconstruction algorithm for releasing anonymized trajectory data and also present how the underlying techniques can be adapted to other anonymity standards. The experimental results on real and synthetic trajectory datasets show the effectiveness of the proposed techniques.

References

[1]

C. C. Aggarwal and P. S. Yu. A condensation approach to privacy preserving data mining. In EDBT'04: 9th International Conference on Extending Database Technology, 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: Proceedings of the 25th ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems, pages 153-162, Chicago, IL, USA, June 26-28 2006.

Digital Library

[3]

V. S. V. Aris Gkoulalas-Divanis. A free terrain model for trajectory k-anonymity. In DEXA'08: 19th International Conference on Database and Expert Systems Applications, pages 49-56, 2008.

Digital Library

[4]

M. Atzori. Weak k-anonymity: A low-distortionmodel for protecting privacy. In S. K. Katsikas, J. Lopez, M. Backes, S. Gritzalis, and B. Preneel, editors, ISC, volume 4176 of Lecture Notes in Computer Science, pages 60-71. Springer, 2006.

Digital Library

[5]

M. Atzori, F. Bonchi, F. Giannotti, and D. Pedreschi. Blocking anonymity threats raised by frequent itemset mining. In ICDM'05: Proceedings of the Fifth IEEE International Conference on Data Mining, pages 561-564, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[6]

M. Atzori, F. Bonchi, F. Giannotti, and D. Pedreschi. Anonymity preserving pattern discovery. The VLDB Journal: The International Journal on Very Large Data Bases, Nov. 2006.

Digital Library

[7]

C. Bettini, X. S.Wang, and S. Jajodia. Protecting privacy against location-based personal identification. In Secure Data Management, pages 185-199, 2005.

Digital Library

[8]

F. Bonchi, O. Abul, and M. Nanni. Never walk alone: Uncertainty for anonymity in moving objects databases. In ICDE'08: Proceedings of the 24nd International Conference on Data Engineering, Cancun, Mexico, Apr. 7 2008.

Digital Library

[9]

J.-W. Byun, A. Kamra, E. Bertino, and N. Li. Efficient k-anonymization using clustering techniques. In DASFAA07: The 12th International Conference on Database Systems for Advanced Applications, Apr. 2007.

Digital Library

[10]

J.-W. Byun, Y. Sohn, E. Bertino, and N. Li. Secure anonymization for incremental datasets. In SDM'06: Third VLDB Workshop on Secure Data Management, Seoul, Korea, Sept. 18 2006.

Digital Library

[11]

L. Chen and R. Ng. The marriage of lp-norms and edit distance, 2004.

Digital Library

[12]

R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar. Preserving user location privacy in mobile datamanagement infrastructures. In 6thWorkshop Privacy Enhancing TechnologyWorkshop, pages 393-412. Springer, 2006.

Digital Library

[13]

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.

[14]

J. Domingo-Ferrer and V. Torra. Ordinal, continuous and heterogeneous k-anonymity through microaggregation. Data Mining and Knowledge Discovery, 11(2):195-212, 2005.

Digital Library

[15]

M. Duckham and L. Kulik. A formal model of obfuscation and negotiation for location privacy. In The International Conference on Pervasive Computing, pages 152-170, 2005.

Digital Library

[16]

EU FP6. Geographic privacy-aware knowledge discovery and delivery (GEOPKDD). http://www.geopkdd.eu, 2005.

[17]

European Parliament. Directive 95/46/ec. http://www.cdt.org/privacy/eudirective/EU_Directive_.html, 1995.

[18]

European Parliament. Regulation (ec) no 45/2001. http://ec.europa.eu/justice home/fsj/privacy/docs/application/286_en.pdf, Dec. 18 2000.

[19]

B. Gedik and L. Liu. Location privacy inmobile systems: A personalized anonymization model. In ICDCS'05: The 25th International Conference on Distributed Computing Systems, 2005.

Digital Library

[20]

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.

Digital Library

[21]

F. Giannotti and D. Pedreschi. Mobility, Data Mining and Privacy. 2008.

Digital Library

[22]

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.

Digital Library

[23]

M. Gruteser and X. Liu. Protecting privacy in continuous location-tracking applications. IEEE Security and Privacy, 02(2):28-34, 2004.

Digital Library

[24]

D. Gusfield. Efficient methods for multiple sequence alignment with guaranteed error bounds. In Bulletin of Mathematical Biology., pages 141-154, 1993.

[25]

Standard for privacy of individually identifiable health information. Federal Register, 66(40), Feb. 28 2001.

[26]

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, pages 194205, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

[27]

B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady. Preserving privacy in GPS traces via densityaware path cloaking. In CCS: ACM Conference on Computer and Communications Security, VA, USA, Oct. 29 2007.

Digital Library

[28]

A. O. hrn and L. Ohno-Machado. Using boolean reasoning to anonymize databases. Artificial Intelligence in Medicine, 15(3):235-254, Mar. 1999.

[29]

T. Jiang and L. Wang. On the complexity of multiple sequence alignment. Journal of Computational Biology, 1:337-348, 1994.

[30]

N. Li and T. Li. t-closeness: Privacy beyond k-anonymity and l-diversity. In ICDE'07: Proceedings of the 23nd International Conference on Data Engineering, Istanbul, Turkey, Apr. 16-20 2007.

[31]

D. Luper, D. Cameron, J. A. Miller, and H. R. Arabnia. Spatial and temporal target association through semantic analysis and GPS data mining. In IKE'07: The 2007World Congress in Computer Science, Computer Engineering, & Applied Computing, Las Vegas, USA, June 25-28 2007.

[32]

A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. In ICDE'06: Proceedings of the 22nd IEEE International Conference on Data Engineering, Atlanta Georgia, Apr. 2006.

Digital Library

[33]

D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the ACM (JACM), 25(2):322-336, 1978.

Digital Library

[34]

T. McGhee. GPS technology tracks employees. http://www.denverpost.com/headlines/ci_4800440, 2006.

[35]

MIT SENSEable City Lab. Real time Rome. http://senseable.mit.edu/realtimerome/, 2006.

[36]

M. F.Mokbel, C.-Y. Chow, andW. 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.

Digital Library

[37]

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.

Digital Library

[38]

M. E. Nergiz and C. Clifton. Thoughts on k-anonymization. Data and Knowledge Engineering, 63(3):622-645, Dec. 2007.

Digital Library

[39]

M. E. Nergiz, C. Clifton, and A. E. Nergiz. Multirelational k-anonymity. IEEE Transactions on Knowledge and Data Engineering, 99(1), 5555.

[40]

Norwich Union. Pay as you drive. http://www.norwichunion.com/ pay-as-you-drive/, 2007.

[41]

P. Samarati. Protecting respondent's privacy in microdata release. IEEE Transactions on Knowledge and Data Engineering, 13(6):1010-1027, Nov./Dec. 2001.

Digital Library

[42]

L. Sweeney. k-Anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness Knowledge-Based Systems, 10(5):557570, 2002.

Digital Library

[43]

M. Terrovitis and N. Mamoulis. Privacy preservation in the publication of trajectories. In MDM'08: Proceedings of the The Ninth International Conference on Mobile Data Management, pages 65-72, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[44]

T. M. Truta and A. Campan. k-anonymization incremental maintenance and optimization techniques. In SAC2007: ACM Symposium on Applied Computing, page 380-387, Seoul, Korea, 2007.

Digital Library

[45]

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.

[46]

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.

Digital Library

Cited By

Miranda-Pascual ÀGuerra-Balboa PParra-Arnau JForné JStrufe T(2024)An overview of proposals towards the privacy-preserving publication of trajectory dataInternational Journal of Information Security10.1007/s10207-024-00894-023:6(3711-3747)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1007/s10207-024-00894-0
Sun SMa SSong JYue WLin XMa T(2022)Experiments and Analyses of Anonymization Mechanisms for Trajectory Data PublishingJournal of Computer Science and Technology10.1007/s11390-022-2409-x37:5(1026-1048)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11390-022-2409-x
Gramaglia MFiore MFurno AStanica R(2021)GLOVE: Towards Privacy-Preserving Publishing of Record-Level-Truthful Mobile Phone TrajectoriesACM/IMS Transactions on Data Science10.1145/34511782:3(1-36)Online publication date: 3-Sep-2021
https://dl.acm.org/doi/10.1145/3451178
Show More Cited By

Index Terms

Towards Trajectory Anonymization: a Generalization-Based Approach

Recommendations

Towards trajectory anonymization: a generalization-based approach
SPRINGL '08: Proceedings of the SIGSPATIAL ACM GIS 2008 International Workshop on Security and Privacy in GIS and LBS

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 ...
Balancing trajectory privacy and data utility using a personalized anonymization model

With the widespread use of location-based services (LBS), the number of trajectories gathered by location service providers is dynamically growing. On the one hand, mining and analyzing these spatiotemporal trajectories can help to work out a mobile-...
Towards identity anonymization on graphs
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

The proliferation of network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of the nodes before publishing the graph/social network data does not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Transactions on Data Privacy

Transactions on Data Privacy Volume 2, Issue 1

April 2009

97 pages

ISSN:1888-5063

EISSN:2013-1631

Issue’s Table of Contents

Publisher

IIIA-CSIC

Bellaterra, Catalonia, Spain

Publication History

Published: 01 April 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
82
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Miranda-Pascual ÀGuerra-Balboa PParra-Arnau JForné JStrufe T(2024)An overview of proposals towards the privacy-preserving publication of trajectory dataInternational Journal of Information Security10.1007/s10207-024-00894-023:6(3711-3747)Online publication date: 4-Sep-2024
https://dl.acm.org/doi/10.1007/s10207-024-00894-0
Sun SMa SSong JYue WLin XMa T(2022)Experiments and Analyses of Anonymization Mechanisms for Trajectory Data PublishingJournal of Computer Science and Technology10.1007/s11390-022-2409-x37:5(1026-1048)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11390-022-2409-x
Gramaglia MFiore MFurno AStanica R(2021)GLOVE: Towards Privacy-Preserving Publishing of Record-Level-Truthful Mobile Phone TrajectoriesACM/IMS Transactions on Data Science10.1145/34511782:3(1-36)Online publication date: 3-Sep-2021
https://dl.acm.org/doi/10.1145/3451178
Abul OBitirgen O(2021)Anonymous location sharing in urban area mobilityKnowledge and Information Systems10.1007/s10115-021-01566-463:7(1849-1871)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10115-021-01566-4
Ward KLin DMadria S(2020)A Parallel Algorithm For Anonymizing Large-scale Trajectory DataACM/IMS Transactions on Data Science10.1145/33686391:1(1-26)Online publication date: 12-Mar-2020
https://dl.acm.org/doi/10.1145/3368639
Tan RTao YSi WZhang Y(2020)Privacy preserving semantic trajectory data publishing for mobile location-based servicesWireless Networks10.1007/s11276-019-02058-826:8(5551-5560)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s11276-019-02058-8
Sopaoglu UAbul O(2020)A utility based approach for data stream anonymizationJournal of Intelligent Information Systems10.1007/s10844-019-00577-654:3(605-631)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1007/s10844-019-00577-6
Dai YShao JWei CZhang DShen H(2018)Personalized semantic trajectory privacy preservation through trajectory reconstructionWorld Wide Web10.1007/s11280-017-0489-221:4(875-914)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11280-017-0489-2
Abul OBayrak C(2018)From location to location pattern privacy in location-based servicesKnowledge and Information Systems10.1007/s10115-017-1146-x56:3(533-557)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10115-017-1146-x
(2017)Trajectory anonymisation based on graph split using EMDInternational Journal of Computational Science and Engineering10.1504/IJCSE.2017.1000502614:3(290-298)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1504/IJCSE.2017.10005026
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents