انتشار پایگاه‌های داده مسیر حرکت با ضمانت حریم خصوصی تفاضلی

نوع مقاله : مقاله پژوهشی

نویسندگان

گروه کامپیوتر، دانشکده مهندسی برق و کامپیوتر، دانشگاه تربیت مدرس، تهران، ایران

چکیده

در سال‌های اخیر، سازوکارهای متعددی برای اجرای پرس‌وجوهای آماری با ضمانت حریم خصوصی تفاضلی روی پایگاه‌های داده مسیر حرکت پیشنهاد شده است. هدف اغلب این سازوکارها پاسخ به پرس‌وجوهای آماری بدون انتشار مسیرهای حرکت اشیا متحرک است. در این مقاله، یک سازوکار حریم خصوصی تفاضلی جدید به نام DP-STDR پیشنهاد می‌شود که با حفظ سودمندی‌های فضایی و زمانی، مسیرهای حرکت مصنوعی را با ضمانت حریم خصوصی تفاضلی و برای اهداف تحلیل داده منتشر می‌کند. DP-STDR برخی ویژگی‌های اصلی فضایی، زمانی و آماری مسیرهای حرکت واقعی را حفظ کرده و ساختار درختی جدیدی را با ضمانت حریم خصوصی تفاضلی برای نگهداری محتمل‌ترین مسیرهای موجود با طول‌ها و نقاط شروع مختلف تعریف می‌کند. از این ساختار درختی برای تولید مسیرهای حرکت مصنوعی استفاده می‌شود. آزمایش‌های انجام‌شده نشان می‌دهند که DP-STDR در مقایسه با کارهای مرتبط پیشین، سودمندی پاسخ پرس‌وجوها را افزایش داده و ویژگی‌های فضایی، زمانی و آماری مسیرهای حرکت واقعی را بهتر حفظ می‌کند.

کلیدواژه‌ها


عنوان مقاله [English]

Trajectory Database Release with Differential Privacy Guarantee

نویسندگان [English]

  • F. Deldar
  • M. Abadi
Tarbiat Modares University
چکیده [English]

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.
 

کلیدواژه‌ها [English]

  • Differential privacy
  • Trajectory database release
  • Noisy path tree
  • Trajectory pattern
[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.##
دوره 9، شماره 1 - شماره پیاپی 33
شماره پیاپی 33، فصلنامه بهار
اردیبهشت 1400
صفحه 29-42
  • تاریخ دریافت: 24 اسفند 1398
  • تاریخ بازنگری: 11 اردیبهشت 1399
  • تاریخ پذیرش: 15 مرداد 1399
  • تاریخ انتشار: 01 اردیبهشت 1400