Al-Hussaeni, Khalil, Fung, Benjamin C.M., Iqbal, Farkhund, Dagher, Gaby G. and Park, Eun G. (2018) SafePath: Differentially-Private Publishing of Passenger Trajectories in Transportation Systems. Computer Networks . ISSN 13891286 (In Press)
Preview |
Text (In Press, Accepted Manuscript) (application/pdf)
3MBSafePath--Differentially-Private-Publishing-of-Passenger-Tra_2018_Computer-N.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Official URL: http://dx.doi.org/10.1016/j.comnet.2018.07.007
Abstract
In recent years, the collection of spatio-temporal data that captures human movements has increased tremendously due to the advancements in hardware and software systems capable of collecting person-specific data. The bulk of the data collected by these systems has numerous applications, or it can simply be used for general data analysis. Therefore, publishing such big data is greatly beneficial for data recipients. However, in its raw form, the collected data contains sensitive information pertaining to the individuals from which it was collected and must be anonymized before publication. In this paper, we study the problem of privacy-preserving passenger trajectories publishing and propose a solution under the rigorous differential privacy model. Unlike sequential data, which describes sequentiality between data items, handling spatio-temporal data is a challenging task due to the fact that introducing a temporal dimension results in extreme sparseness. Our proposed solution introduces an efficient algorithm, called SafePath, that models trajectories as a noisy prefix tree and publishes ϵ-differentially-private trajectories while minimizing the impact on data utility. Experimental evaluation on real-life transit data in Montreal suggests that SafePath significantly improves efficiency and scalability with respect to large and sparse datasets, while achieving comparable results to existing solutions in terms of the utility of the sanitized data.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Concordia Institute for Information Systems Engineering |
|---|---|
| Item Type: | Article |
| Refereed: | Yes |
| Authors: | Al-Hussaeni, Khalil and Fung, Benjamin C.M. and Iqbal, Farkhund and Dagher, Gaby G. and Park, Eun G. |
| Journal or Publication: | Computer Networks |
| Date: | 7 July 2018 |
| Funders: |
|
| Digital Object Identifier (DOI): | 10.1016/j.comnet.2018.07.007 |
| Keywords: | Differential privacy; trajectory data; sparse data; smart city; transportation |
| ID Code: | 984060 |
| Deposited By: | Monique Lane |
| Deposited On: | 18 Jul 2018 17:14 |
| Last Modified: | 07 Jul 2020 00:00 |
References:
S. Abraham, P.S. Lal Spatio-temporal similarity of network-constrained moving object trajectories using sequence alignment of travel locations Transportation Research Part C: Emerging Technologies, 23 (2012), pp. 109-123Data Management in Vehicular Networks
O. Abul, F. Bonchi, M. Nanni Never walk alone: Uncertainty for anonymity in moving objects databases Proceedings of the 24th IEEE International Conference on Data Engineering, ICDE ’08 (2008), pp. 376-385
R. Agrawal, R. Srikant Mining sequential patterns Proceedings of the 11th International Conference on Data Engineering, ICDE ’95 (1995) 3–14
R. Assam, M. Hassani, T. Seidl Differential private trajectory protection of moving objects
Proceedings of the 3rd ACM SIGSPATIAL International Workshop on GeoStreaming, IWGS ’12 (2012), pp. 68-77
B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, K. Talwar Privacy, accuracy, and consistency too: A holistic solution to contingency table release Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’07 (2007)
M. Burger, M. van den Berg, A. Hegyi, B.D. Schutter, J. Hellendoorn Considerations for model-based traffic control Transportation Research Part C: Emerging Technologies, 35 (2013), pp. 1-19
Y. Cao, M. Yoshikawa Differentially private real-time data release over infinite trajectory streams Proceedings of the 16th IEEE International Conference on Mobile Data Management - Volume 02, MDM ’15 (2015), pp. 68-73
R. Chen, G. Acs, C. Castelluccia Differentially private sequential data publication via variable-length n-grams Proceedings of the ACM Conference on Computer and Communications Security, CCS ’12 (2012), pp. 638-649
R. Chen, B.C. Fung, B.C. Desai, N.M. Sossou Differentially private transit data publication: A case study on the montreal transportation system Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’12 (2012), pp. 213-221
R. Chen, B.C.M. Fung, N. Mohammed, B.C. Desai Privacy-preserving trajectory data publishing by local suppression Information Sciences: Special Issue on Data Mining for Information Security, 231 (2013), pp. 83-97
A.E. Cicek, M.E. Nergiz, Y. Saygin Ensuring location diversity in privacy-preserving spatio-temporal data publishing The VLDB Journal, 23 (4) (2014), pp. 609-625
B. Coifman, D. Beymer, P. McLauchlan, J. Malik A real-time computer vision system for vehicle tracking and traffic surveillance Transportation Research Part C: Emerging Technologies, 6 (4) (1998), pp. 271-288
G. Cormode, C. Procopiuc, D. Srivastava, T.T.L. Tran Differentially private summaries for sparse data Proceedings of the 15th International Conference on Database Theory, ICDT ’12 (2012), pp. 299-311
C. Dwork Differential privacy Proceedings of the 33rd International Conference on Automata, Languages and Programming - Volume Part II, ICALP’06 (2006), pp. 1-12
C. Dwork Differential privacy: A survey of results Proceedings of the 5th International Conference on Theory and Applications of Models of Computation, TAMC’08 (2008), pp. 1-19
C. Dwork A firm foundation for private data analysis Communications of the ACM, 54 (1) (2011), pp. 86-95
C. Dwork, F. McSherry, K. Nissim, A. Smith Calibrating noise to sensitivity in private data analysis Proceedings of the 3rd Conference on Theory of Cryptography, TCC’06 (2006), pp. 265-284
E. ElSalamouny, S. Gambs Differential privacy models for location-based services
Transactions on Data Privacy, 9 (1) (2016) 15–48
L. Fan, L. Xiong, V. Sunderam Differentially private multi-dimensional time series release for traffic monitoring Proceedings of the 27th Annual IFIP WG 11.3 Conference on Data and Applications Security and Privacy XXVII - Volume 7964, DBSec 2013 (2013), pp. 33-48
L. Fan, L. Xiong, V. Sunderam Fast: Differentially private real-time aggregate monitor with filtering and adaptive sampling Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’13(2013), pp. 1065-1068
S. Gambs, M.-O. Killijian, M.N.n. del Prado Cortez Show me how you move and i will tell you who you are Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS, SPRINGL ’10 (2010), pp. 34-41
S.R. Ganta, S.P. Kasiviswanathan, A. Smith Composition attacks and auxiliary information in data privacy Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08 (2008), pp. 265-273
M. Ghasemzadeh, B.C. Fung, R. Chen, A. Awasthi Anonymizing trajectory data for passenger flow analysis Transportation Research Part C: Emerging Technologies, 39 (2014), pp. 63-79
P.J. Haas, A.N. Swami Sequential sampling procedures for query size estimation Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’92(1992), pp. 341-350
M. Hay, V. Rastogi, G. Miklau, D. Suciu Boosting the accuracy of differentially private histograms through consistency Proceedings of the VLDB Endowment, 3 (1-2) (2010), pp. 1021-1032
X. He, G. Cormode, A. Machanavajjhala, C.M. Procopiuc, D. Srivastava pt: Differentially private trajectory synthesis using hierarchical reference systems Proceedings of the VLDB Endowment, 8 (11) (2015), pp. 1154-1165
S.-S. Ho Preserving privacy for moving objects data mining Proceedings of the IEEE International Conference on Intelligence and Security Informatics (ISI) (2012), pp. 135-137
S.-S. Ho, S. Ruan Preserving privacy for interesting location pattern mining from trajectory data Transactions on Data Privacy, 6 (1) (2013), pp. 87-106
H. Hu, J. Xu, S.T. On, J. Du, J.K.-Y. Ng Privacy-aware location data publishing ACM Transactions on Database Systems (TODS), 35 (2010), pp. 18:1-18:42
K. Jiang, D. Shao, S. Bressan, T. Kister, K.-L. Tan Publishing trajectories with differential privacy guarantees Proceedings of the 25th International Conference on Scientific and Statistical Database Management, SSDBM (2013), pp. 12:1-12:12
D. Kifer Attacks on privacy and definetti’s theorem Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’09(2009), pp. 127-138
D. Leoni Non-interactive differential privacy: A survey Proceedings of the 1st International Workshop on Open Data, WOD ’12 (2012), pp. 40-52
X. Li, J. Han, J.-G. Lee, H. Gonzalez Traffic density-based discovery of hot routes in road networks Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases, SSTD’07 (2007), pp. 441-459
A. Machanavajjhala, D. Kifer, J. Gehrke, M. Venkitasubramaniam L-diversity: Privacy beyond k-anonymity 1 (2007)
F. McSherry Privacy integrated queries Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’09(2009), pp. 19-30
F. McSherry, K. Talwar Mechanism design via differential privacy Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’07(2007), pp. 94-103
A. Monreale, G. Andrienko, N. Andrienko, F. Giannotti, D. Pedreschi, S. Rinzivillo, S. Wrobel Movement data anonymity through generalization Transactions on Data Privacy, 3 (2) (2010), pp. 91-121
M.E. Nergiz, M. Atzori, Y. Saygin Towards trajectory anonymization: A generalization-based approach Proceedings of the SIGSPATIAL ACM GIS International Workshop on Security and Privacy in GIS and LBS, SPRINGL ’08 (2008), pp. 52-61
R.G. Pensa, A. Monreale, F. Pinelli, D. Pedreschi Pattern-preserving k-anonymization of sequences and its application to mobility data mining Proceedings of the 1st International Workshop on Privacy in Location-Based Applications (2008)
V. Primault, S.B. Mokhtar, C. Lauradoux, L. Brunie Time distortion anonymization for the publication of mobility data with high utility Proceedings of the 14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (2015), pp. 539-546
W. Qardaji, W. Yang, N. Li Understanding hierarchical methods for differentially private histograms Proceedings of the VLDB Endowment, 6 (14) (2013), pp. 1954-1965
R. Sherkat, J. Li, N. Mamoulis Efficient time-stamped event sequence anonymization ACM Transactions on the Web (TWEB), 8 (1) (2013), pp. 4:1-4:53
L. Sweeney K-anonymity: A model for protecting privacy International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10 (5) (2002), pp. 557-570
L.-A. Tang, Y. Zheng, J. Yuan, J. Han, A. Leung, W.-C. Peng, T.L. Porta A framework of traveling companion discovery on trajectory data streams ACM Transactions on Intelligent Systems and Technology (TIST), 5 (1) (2014), pp. 3:1-3:34
M. Terrovitis, N. Mamoulis Privacy preservation in the publication of trajectories Proceedings of the The Ninth International Conference on Mobile Data Management, MDM ’08 (2008), pp. 65-72
J. Wang, S. Liu, Y. LiA review of differential privacy in individual data release
International Journal of Distributed Sensor Networks, 2015 (2016), pp. 1:1-1:1
R.C.-W. Wong, A.W.-C. Fu, K. Wang, J. Pei Minimality attack in privacy preserving data publishing Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB ’07 (2007), pp. 543-554
X. Xiao, G. Bender, M. Hay, J. Gehrke ireduct: Differential privacy with reduced relative errors Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD ’11(2011), pp. 229-240
X. Xiao, G. Wang, J. Gehrke Differential privacy via wavelet transforms IEEE Transactions on Knowledge and Data Engineering (TKDE), 23 (8) (2011), pp. 1200-1214
Y. Xiao, L. Xiong Protecting locations with differential privacy under temporal correlations
Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15(2015), pp. 1298-1309
R. Yarovoy, F. Bonchi, L.V.S. Lakshmanan, W.H. Wang Anonymizing moving objects: how to hide a mob in a crowd? Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT ’09 (2009), pp. 72-83
D. Zekri, B. Defude, T. Delot Building, sharing and exploiting spatio- temporal aggregates in vehicular networks Mobile Information Systems, 10 (3) (2014), pp. 259-285
Y. Zheng, N.J. Yuan, K. Zheng, S. Shang On discovery of gathering patterns from trajectories Proceedings of the IEEE International Conference on Data Engineering, ICDE ’13 (2013), pp. 242-253
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.
Repository Staff Only: item control page
Download Statistics
Download Statistics