Trajectory Database Release with Differential Privacy Guarantee

Document Type : Original Article

Authors

Tarbiat Modares University

Abstract

Over the last years, several differentially private mechanisms have been proposed to answer statistical   queries over trajectory databases. However, most of these mechanisms aim to answer statistical queries without releasing  trajectories. In this paper, we present DP-STDR; a new differentially private           mechanism that releases synthetic  trajectories for data analysis purposes while preserving spatial and temporal utilities. DP-STDR keeps some main spatial, temporal, and statistical properties of original         trajectories and defines a new differentially private tree      structure to keep the most probable paths with different lengths and different starting points. This tree structure is used to generate synthetic trajectories. Our experiments show that DP-STDR enhances the utility of query answers and  better preserves the main spatial, temporal, and statistical properties of original trajectories in comparison to prior related work.
 

Keywords


[1]     B. C. M. Fung, K. Wang, R. Chen, and P. S. Yu,       “Privacy-preserving data publishing: A survey of recent develop­ments,” ACM Comput. Surv., vol. 42, no. 4, pp.     1–14, Jun. 2010.##
[2]     C. Dwork, “Differential privacy,” In Automata, Languages and Programming (M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, eds.), Lecture Notes in Computer Science, pp. 1–12, Berlin, Heidelberg, Germany: Springer, 2006.##
[3]     T. Zhu, G. Li, W. Zhou, and P. S. Yu, “Differentially private data publishing and analysis: A survey,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 8, pp. 1619–1638, Aug. 2017.##
[4]     N. Niknami, M. Abadi, and F. Deldar, “SpatialPDP: A personalized differentially private mechanism for range counting queries over spatial databases,” In Proceedings of the 2014 4th International Conference on Computer and Knowledge Engineering, Mashhad, Iran, pp. 709–715, Oct. 2014.##
[5]     F. Deldar and M. Abadi, “PLDP-TD: Personalized-location differentially private data analysis on trajectory databases,” Pervasive Mob. Comput., vol. 49, pp. 1–22, Sep. 2018.##
[6]     G. Cormode, T. Kulkarni, and D. Srivastava, “Answering range queries under local differential privacy,” Proc. VLDB Endow., vol. 12, no. 10, pp. 1126–1138, Jun. 2019.##
[7]     K. Al-Hussaeni, B. C. M. Fung, F. Iqbal, J. Liu, and P. C. K. Hung, “Differentially private multidimensional data publish­ing,” Knowl. Inf. Syst., vol. 56, no. 3, pp. 717–752, Sep. 2018.##
[8]      C. Piao, Y. Shi, J. Yan, C. Zhang, and L. Liu,          “Privacy-preserving governmental data publishing: A      fog-computing-based differential privacy approach,” Future Gener. Comput. Syst., vol. 90, pp. 158–174, Jan. 2019.##
[9]     Z. Zheng, T. Wang, J. Wen, S. Mumtaz, A. K. Bashir, and S. H. Chauhdary, “Differentially private high-dimensional data publication in Internet of Things,” IEEE Internet Things J., vol. 7, no. 4, pp. 1–10, Apr. 2020.##
[10]  R. Chen, B. C. M. Fung, B. C. Desai, and N. M. Sossou, “Differentially private transit data publication: A case study on the Montreal transportation system,” In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, pp. 213–221, Aug. 2012.##
[11]  X. He, G. Cormode, A. Machanavajjhala, C. M. Procopiuc, and D. Srivastava, “DPT: Differentially private trajectory synthesis using hierarchical reference systems,” Proc. VLDB Endow., vol. 8, pp. 1154–1165, Jul. 2015.##
[12]  S. Wang, R. Sinnott, and S. Nepal, “Privacy-protected   statis­tics publication over social media user trajectory streams,” Future Gener. Comput. Syst., vol. 87, pp. 792–802, Oct. 2018.##
[13]  F. Deldar and M. Abadi, “PDP-SAG: Personalized privacy protection in moving objects databases by combining    differ­ential privacy and sensitive attribute generalization,” IEEE Access, vol. 7, pp. 85887–85902, Jun. 2019.##
[14]  M. E. Gursoy, L. Liu, S. Truex, L. Yu, and W. Wei,  “Utility-aware synthesis of differentially private and attack-resilient location traces,” In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, Toronto, Canada, pp. 196–211, Jan. 2018.##
[15]  M. E. Gursoy, L. Liu, S. Truex, and L. Yu, “Differentially private and utility preserving publication of trajectory data,” IEEE Trans. Mob. Comput., vol. 18, no. 10, pp. 2315–2329, Oct. 2019.##
[16]  N. Holohan, D. J. Leith, and O. Mason, “Differential privacy in metric spaces: Numerical, categorical and functional data under the one roof,” Inf. Sci., vol. 305, pp. 256–268, Jun. 2015.##
[17]  J. Zhang, X. Xiao, and X. Xie, “PrivTree: A differentially private algorithm for hierarchical decompositions,” In Proceedings of the 2016 ACM SIGMOD International    Con­ference on Management of Data, San Francisco, CA, USA, pp. 155–170, Jun. 2016.##
[18]  C. Xu, J. Ren, Y. Zhang, Z. Qin, and K. Ren, “DPPro: Differentially private high-dimensional data release via random projection,” IEEE Trans. Inf. Forensics Secur., vol. 12, no. 12, pp. 3081–3093, Dec. 2017.##
[19]  G. Cormode, S. Jha, T. Kulkarni, N. Li, D. Srivastava, and T. Wang, “Privacy at scale: Local differential privacy in practice,” In Proceedings of the 2018 ACM SIGMOD Interna­tional Conference on Management of Data, Houston, TX, USA, pp. 1655–1658, May 2018.##
[20]  F. Deldar and M. Abadi, “Differentially private count queries over personalized-location trajectory databases,” Data Brief, vol. 20, pp. 1510–1514, Oct. 2018.##
[21]  R. Chen, G. Acs, and C. Castelluccia, “Differentially private sequential data publication via variable-length n-grams,” In Proceedings of the 2012 ACM SIGSAC Conference on Computer and Communications Security, Raleigh, NC, USA, pp. 638–649, Oct. 2012.##
[22]  S. Wang and R. O. Sinnott, “Protecting personal trajectories of social media users through differential privacy,” Comput. Secur., vol. 67, pp. 142–163, Jun. 2017.##
[23]  M. Li, L. Zhu, Z. Zhang, and R. Xu, “Achieving differential privacy of trajectory data publishing in participatory sensing,” Inf. Sci., vol. 400, pp. 1–13, Aug. 2017.##
[24]  C. Dwork, F. McSherry, K. Nissim, and A. Smith,  “Calibrat­ing noise to sensitivity in private data analysis,” In Theory of Cryptography (S. Halevi and T. Rabin, eds.), Lecture Notes in Computer Science, pp. 265–284, Berlin, Heidelberg, Germany: Springer, 2006.##
[25]  F. McSherry and K. Talwar, “Mechanism design via differential privacy,” In Proceedings of the 2007 48th Annual IEEE Symposium on Foundations of Computer Science, Providence, RI, USA, pp. 94–103, Oct. 2007.##
[26]  Z. Jorgensen, T. Yu, and G. Cormode, “Conservative or liberal? personalized differential privacy,” In Proceedings of the 2015 IEEE 31st International Conference on Data    Engi­neering, Seoul, South Korea, pp. 1023–1034, Apr. 2015.##
[27]  N. Kohli and P. Laskowski, “Epsilon voting: Mechanism design for parameter selection in differential privacy,” In Proceedings of the 2018 IEEE Symposium on            Privacy-Aware Computing, Washington, DC, USA, pp.     19–30, Sep. 2018.##
[28]  Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma, “Mining interesting locations and travel sequences from GPS trajecto­ries,” In Proceedings of the 18th International Conference on World Wide Web, Madrid, Spain, pp. 791–800, Apr. 2009.##
[29]  W. Qardaji, W. Yang, and N. Li, “Differentially private grids for geospatial data,” In Proceedings of the 2013 IEEE 29th International Conference on Data Engineering, Brisbane, Australia, pp. 757–768, Apr. 2013.##
Volume 9, Issue 1 - Serial Number 33
Serial No. 33, Spring Quarterly
April 2021
Pages 29-42
  • Receive Date: 14 March 2020
  • Revise Date: 30 April 2020
  • Accept Date: 05 August 2020
  • Publish Date: 21 April 2021