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

research-article

Trajectory anonymity in publishing personal mobility data

Authors:

Francesco Bonchi,

Laks V.S. Lakshmanan,

Hui (Wendy) WangAuthors Info & Claims

ACM SIGKDD Explorations Newsletter, Volume 13, Issue 1

Pages 30 - 42

https://doi.org/10.1145/2031331.2031336

Published: 31 August 2011 Publication History

Abstract

Recent years have witnessed pervasive use of location-aware devices such as GSM mobile phones, GPS-enabled PDAs, location sensors, and active RFID tags. The use of these devices generates a huge collection of spatio-temporal data, variously called moving object data, trajectory data, or moblity data. These data can be used for various data analysis purposes such as city traffic control, mobility management, urban planning, and location-based service advertisements. Clearly, the spatio-temporal data so collected may help an attacker to discover personal and sensitive information like user habits, social customs, religious and sexual preferences of individuals. Consequently, it raises serious concerns about privacy. Simply replacing users' real identifiers (name, SSN, etc.) with pseudonyms is insufficient to guarantee anonymity. The problem is that due to the existence of quasi-identifiers, i.e., spatio-temporal data points that can be linked to external information to re-identify individuals, the attacker may be able to trace the anonymous spatio-temporal data back to individuals.

In this survey, we discuss recent advancement on anonymity preserving data publishing of moving object databases in an off-line fashion. We first introduce several anonymity models, then we describe in detail some of the proposed techniques to enforce trajectory anonymity, discussing their merits and limitations. We conclude by identifying challenging open problems that need attention.

References

[1]

Abul, O., Bonchi, F., and Giannotti, F. Hiding sequential and spatiotemporal patterns. IEEE Trans. Knowl. Data Eng. 22, 12 (2010), 1709--1723.

Digital Library

[2]

Abul, O., Bonchi, F., and Nanni, M. Never Walk Alone: Uncertainty for anonymity in moving objects databases. In Proc. of the 24nd IEEE Int. Conf. on Data Engineering (ICDE'08).

Digital Library

[3]

Abul, O., Bonchi, F., and Nanni, M. Anonymization of moving objects databases by clustering and perturbation. Inf. Syst. 35, 8 (2010), 884--910.

Digital Library

[4]

Aggarwal, C. C., and Yu, P. S. A condensation approach to privacy preserving data mining. In Proc. of the 9th Int. Conf. on Extending Database Technology, (EDBT'04).

[5]

Aggarwal, C. C., and Yu, P. S. On anonymization of string data. In Proc. of the 2007 SIAM Int. Conf. on Data Mining.

[6]

Agrawal, R., Imieliński, T., and Swami, A. Mining association rules between sets of items in large databases. SIGMOD Record 22 (June 1993), 207--216.

Digital Library

[7]

Agrawal, R., and Srikant, R. Fast algorithms for mining association rules in large databases. In Proceedings of the 20th International Conference on Very Large Data Bases (1994), pp. 487--499.

Digital Library

[8]

Akbarinia, R., Pacitti, E., and Valduriez, P. Best position algorithms for top-k queries. In Proceedings of the 33rd international conference on Very large data bases (2007), pp. 495--506.

Digital Library

[9]

Ashbrook, D., and Starner, T. Using gps to learn significant locations and predict movement across multiple users. Personal and Ubiquitous Computing 7, 5 (2003), 275--286.

Digital Library

[10]

Atallah, M. J. Algorithms and Theory of Computation Handbook. CRC Press, 1998.

Digital Library

[11]

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).

Digital Library

[12]

Bonchi, F. Privacy preserving publication of moving object data. In Privacy in Location-Based Applications (2009), C. Bettini, S. Jajodia, P. Samarati, and X. S. Wang, Eds., pp. 190--215.

Digital Library

[13]

Bonchi, F., Saygin, Y., Verykios, V. S., Atzori, M., Gkoulalas-Divanis, A., Kaya, S. V., and Savas, E. Privacy in spatiotemporal data mining. In Mobility, Data Mining and Privacy, F. Giannotti and D. Pedreschi, Eds. Springer, 2008, pp. 297--333.

[14]

Brinkhoff, T. Generating traffic data. IEEE Data Eng. Bull. 26, 2 (2003), 19--25.

[15]

Byun, J.-W., Kamra, A., Bertino, E., and Li, N. Efficient k-anonymization using clustering techniques. In Proc. of the 12th Int. Conf. Database Systems for Advanced Applications, (DASFAA'07).

Digital Library

[16]

Chen, L., Özsu, M. T., and Oria, V. Robust and fast similarity search for moving object trajectories. In Proc. of the 2005 ACM SIGMOD Int. Conf. on Management of Data (SIGMOD'05).

Digital Library

[17]

Dong, X., Zheng, Z., and Niu, Z. Mining infrequent itemsets based on multiple level minimum supports. Second International Conference on Innovative Computing,Information and Control, (ICICIC '07).

Digital Library

[18]

Duckham, M., and Kulik, L. A Formal Model of Obfuscation and Negotiation for Location Privacy. In Proc. of the Third Int. Conf. on Pervasive Computing (Pervasive 2005) (2005), pp. 152--170.

Digital Library

[19]

Fagin, R., Lotem, A., and Naor, M. Optimal aggregation algorithms for middleware. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (2001), pp. 102--113.

Digital Library

[20]

Fagin, R., Lotem, A., and Naor, M. Optimal aggregation algorithms for middleware. Journal of Computer System and Science 66 (June 2003), 614--656.

Digital Library

[21]

Galil, Z., and Italiano, G. F. Data structures and algorithms for disjoint set union problems. ACM Comput. Surv. 23 (September 1991), 319--344.

Digital Library

[22]

Gedik, B., and Liu, L. Location Privacy in Mobile Systems: A Personalized Anonymization Model. In Proc. of the 25th Int. Conf. on Distributed Computing Systems (ICDCS'05).

Digital Library

[23]

Ghinita, G. Private queries and trajectory anonymization: a dual perspective on location privacy. Trans. Data Privacy 2 (April 2009), 3--19.

Digital Library

[24]

Ghinita, G., Damiani, M. L., Silvestri, C., and Bertino, E. Preventing velocity-based linkage attacks in location-aware applications. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2009), pp. 246--255.

Digital Library

[25]

Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., and Tan, K.-L. Private queries in location based services: anonymizers are not necessary. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data (2008), SIGMOD '08, pp. 121--132.

Digital Library

[26]

Ghinita, G., Zhao, K., Papadias, D., and Kalnis, P. A reciprocal framework for spatial k-anonymity. Information System 35 (May 2010), 299--314.

Digital Library

[27]

gil Lee, J., and Han, J. Trajectory clustering: A partition-and-group framework. In Proc. of the 2007 ACM SIGMOD Int. Conf. on Management of Data (SIGMOD'07) (2007), pp. 593--604.

Digital Library

[28]

gil Lee, J., Han, J., and Li, X. Trajectory outlier detection: A partition-and-detect framework. In Proc. of the 24th IEEE International Conference on Data Engineering (ICDE'08) (2008).

Digital Library

[29]

gil Lee, J., Han, J., Li, X., and Gonzalez, H. Traclass: Trajectory classification using hierarchical region-based and trajectory-based clustering ? abstract. In Proc. of the 34th Int. Conf. on Very Large Databases (VLDB'08) (2008).

Digital Library

[30]

Gkoulalas-Divanis, A., Kalnis, P., and Verykios, V. S. Providing k-anonymity in location based services. SIGKDD Explore Newsletter 12 (November 2010), 3--10.

Digital Library

[31]

Gruteser, M., and Grunwald, D. Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking. In Proc. of the First Int. Conf. on Mobile Systems, Applications, and Services (MobiSys 2003).

Digital Library

[32]

Gruteser, M., and Hoh, B. On the Anonymity of Periodic Location Samples. In Proc. of the Second Int. Conf. of Security in Pervasive Computing (SPC 2005) (2005), pp. 179--192.

Digital Library

[33]

Gruteser, M., and Liu, X. Protecting Privacy in Continuous Location-Tracking Applications. IEEE Security & Privacy Magazine 2, 2 (2004), 28--34.

Digital Library

[34]

Hilbert, D. Über die stetige abbildung einer linie auf ein flächenstück. Math. Ann. 38 (1891), 459--460.

[35]

Hoh, B., Gruteser, M., Xiong, H., and Alrabady, A. Preserving privacy in gps traces via uncertaintyaware path cloaking. In Proceedings of the 14th ACM conference on Computer and communications security (2007), pp. 161--171.

Digital Library

[36]

Jeung, H., Liu, Q., Shen, H. T., and Zhou, X. A hybrid prediction model for moving objects. In Proc. of the 24th IEEE International Conference on Data Engineering (ICDE'08) (2008).

Digital Library

[37]

Jin, W., LeFevre, K., and Patel, J. M. An online framework for publishing privacy-sensitive location traces. In Proceedings of the Ninth ACM International Workshop on Data Engineering for Wireless and Mobile Access (2010).

Digital Library

[38]

Kido, H., Yanagisawa, Y., and Satoh, T. Protection of Location Privacy using Dummies for Locationbased Services. In Proc. of the 21st IEEE Int. Conf. on Data Engineering (ICDE'05).

Digital Library

[39]

Kido, H., Yanagisawa, Y., and Satoh, T. An Anonymous Communication Technique using Dummies for Location-based Services. In Proc. of the Third Int. Conf. on Pervasive Computing (Pervasive 2005) (2005), pp. 88--97.

[40]

Krishnamachari, B., Ghinita, G., and Kalnis, P. Privacy-preserving publication of user locations in the proximity of sensitive sites. In Proceedings of the 20th international conference on Scientific and Statistical Database Management (2008), SSDBM '08, pp. 95--113.

Digital Library

[41]

Krumm, J. Inference attacks on location tracks. In the Proceedings of the Fifth International Conference on Pervasive Computing (Pervasive) (2007).

Digital Library

[42]

Li, X., Han, J., Kim, S., and Gonzalez, H. Anomaly detection in moving object.

[43]

Li, X., Han, J., Lee, J.-G., and Gonzalez, H. Traffic density-based discovery of hot routes in road networks.

[44]

Mamoulis, N., Cao, H., Kollios, G., Hadjieleftheriou, M., Tao, Y., and Cheung, D. W. Mining, indexing, and querying historical spatiotemporal data.

[45]

Mohammed, N., Fung, B. C., and Debbabi, M. Walking in the crowd: anonymizing trajectory data for pattern analysis. In Proceeding of the 18th ACM conference on Information and knowledge management (2009), pp. 1441--1444.

Digital Library

[46]

Mokbel, M. F., Chow, C.-Y., and Aref, W. G. Casper: Query processing for location services without compromising privacy. In Proceeding of the 32nd International Conference on Very Large Databases (VLDB'06).

Digital Library

[47]

Mokbel, M. F., Chow, C.-Y., and Aref, W. G. The new casper: A privacy-aware location-based database server. In Proc. of the 23rd IEEE International Conference on Data Engineering (ICDE'07).

Digital Library

[48]

Monreale, A., Trasarti, R., Renso, C., Pedreschi, D., and Bogorny, V. Preserving privacy in semantic-rich trajectories of human mobility. In Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS (2010), pp. 47--54.

Digital Library

[49]

Nanni, M., and Pedreschi, D. Time-focused clustering of trajectories of moving objects. Journal of Intelligent Information Systems 27, 3 (2006), 267--289.

Digital Library

[50]

Nergiz, E., Atzori, M., and Saygin, Y. Towards trajectory anonymization: a generalization-based approach. In Proc. of ACM GIS Workshop on Security and Privacy in GIS and LBS (2008).

Digital Library

[51]

Papadopoulos, S., Bakiras, S., and Papadias, D. Nearest neighbor search with strong location privacy. Proc. VLDB Endow. 3 (September 2010), 619--629.

Digital Library

[52]

Samarati, P., and Sweeney, L. Generalizing data to provide anonymity when disclosing information (abstract). In Proc. of the 17th ACM Symp. on Principles of Database Systems (PODS'98).

Digital Library

[53]

Samarati, P., and Sweeney, L. Protecting Privacy when Disclosing Information: k-Anonymity and its Enforcement Through Generalization and Suppresion. In Proc. of the IEEE Symp. on Research in Security and Privacy (1998), pp. 384--393.

[54]

Spaccapietra, S., Parent, C., Damiani, M. L., de Macedo, J. A., Porto, F., and Vangenot, C. A conceptual view on trajectories. Data Knowledge Engineering 65 (April 2008), 126--146.

Digital Library

[55]

Sweeney, L. k-anonymity privacy protection using generalization and suppression. International Journal on Uncertainty Fuzziness and Knowledge-based Systems 10, 5 (2002).

Digital Library

[56]

Terrovitis, M., and Mamoulis, N. Privacy preservation in the publication of trajectories. In Proc. of the 9th Int. Conf. on Mobile Data Management (MDM'08).

Digital Library

[57]

Yarovoy, R., Bonchi, F., Lakshmanan, L. V. S., and Wang, W. H. Anonymizing moving objects: How to hide a MOB in a crowd? In Proc. of the 12th Int. Conf. on Extending Database Technology (EDBT'09).

Digital Library

[58]

Zheng, Y., Zhang, L., Xie, X., and Ma, W.-Y. Mining interesting locations and travel sequences from gps trajectories. In Proceedings of the 18th international conference on World wide web (2009), pp. 791--800.

Digital Library

Cited By

Liu YKennedy LAmiri HZüfle A(2024)Neural Collaborative Filtering to Detect Anomalies in Human Semantic TrajectoriesProceedings of the 1st ACM SIGSPATIAL International Workshop on Geospatial Anomaly Detection10.1145/3681765.3698463(79-89)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3681765.3698463
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
Nelson J(2023)Cartography & geovisual analytics in personal contexts: designing for the data creatorInternational Journal of Cartography10.1080/23729333.2023.21894319:2(210-230)Online publication date: 4-Apr-2023
https://doi.org/10.1080/23729333.2023.2189431
Show More Cited By

Index Terms

Trajectory anonymity in publishing personal mobility data

Recommendations

Enhanced P-Sensitive K-Anonymity Models for Privacy Preserving Data Publishing

Publishing data for analysis from a micro data table containing sensitive attributes, while maintaining individual privacy, is a problem of increasing significance today. The k-anonymity model was proposed for privacy preserving data publication. While ...
Privacy-Preserving Data Publishing: An Overview
Anonymity in data publishing and distribution

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGKDD Explorations Newsletter

ACM SIGKDD Explorations Newsletter Volume 13, Issue 1

June 2011

79 pages

ISSN:1931-0145

EISSN:1931-0153

DOI:10.1145/2031331

Issue’s Table of Contents

Copyright © 2011 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 August 2011

Published in SIGKDD Volume 13, Issue 1

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
717
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)1

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu YKennedy LAmiri HZüfle A(2024)Neural Collaborative Filtering to Detect Anomalies in Human Semantic TrajectoriesProceedings of the 1st ACM SIGSPATIAL International Workshop on Geospatial Anomaly Detection10.1145/3681765.3698463(79-89)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3681765.3698463
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
Nelson J(2023)Cartography & geovisual analytics in personal contexts: designing for the data creatorInternational Journal of Cartography10.1080/23729333.2023.21894319:2(210-230)Online publication date: 4-Apr-2023
https://doi.org/10.1080/23729333.2023.2189431
Li STian HShen HSang Y(2023)Differential-Privacy Preserving Trajectory Data Publishing for Road NetworksRecent Challenges in Intelligent Information and Database Systems10.1007/978-3-031-42430-4_46(558-571)Online publication date: 29-Sep-2023
https://doi.org/10.1007/978-3-031-42430-4_46
Liu ZShi WYu YChen PYu Chen B(2022)A LSTM-based approach for modelling the movement uncertainty of indoor trajectories with mobile sensing dataInternational Journal of Applied Earth Observation and Geoinformation10.1016/j.jag.2022.102758108(102758)Online publication date: Apr-2022
https://doi.org/10.1016/j.jag.2022.102758
Ullah IBoreli RKanhere S(2022)Privacy in targeted advertising on mobile devices: a surveyInternational Journal of Information Security10.1007/s10207-022-00655-x22:3(647-678)Online publication date: 24-Dec-2022
https://dl.acm.org/doi/10.1007/s10207-022-00655-x
Li STian HShen HSang Y(2021)Privacy-Preserving Trajectory Data Publishing by Dynamic Anonymization with Bounded DistortionISPRS International Journal of Geo-Information10.3390/ijgi1002007810:2(78)Online publication date: 16-Feb-2021
https://doi.org/10.3390/ijgi10020078
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
Xu FLi YTu ZChang SHuang H(2021)No More than What I Post: Preventing Linkage Attacks on Check-in ServicesIEEE Transactions on Mobile Computing10.1109/TMC.2019.294741620:2(620-633)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1109/TMC.2019.2947416
N RAbraham SDas S(2021)Privacy preserved spatio-temporal trajectory publication of Covid-19 patientsJournal of Location Based Services10.1080/17489725.2021.1906965(1-29)Online publication date: 11-Apr-2021
https://doi.org/10.1080/17489725.2021.1906965
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents