Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (3): 763-768.DOI: 10.11772/j.issn.1001-9081.2018071541

Previous Articles     Next Articles

Crowdsourcing location data collection for local differential privacy

HUO Zheng1, ZHANG Kun2, HE Ping1, WU Yanbin3   

  1. 1. School of Information Technology, Hebei University of Economics and Business, Shijiazhuang Hebei 050061, China;
    2. School of Information Science and Engineering, Hebei University of Science and Technology, Shijiazhuang Hebei 050081, China;
    3. School of Management Science and Engineering, Hebei University of Economics and Business, Shijiazhuang Hebei 050061, China
  • Received:2018-07-23 Revised:2018-09-11 Online:2019-03-10 Published:2019-03-11
  • Contact: 武彦斌
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61502279), the Natural Science Foundation of Hebei Province (F2018210109), the Scientific Research Project of Colleges and Universities in Hebei Province (ZD2018105, QN2018116).


霍峥1, 张坤2, 贺萍1, 武彦斌3   

  1. 1. 河北经贸大学 信息技术学院, 石家庄 050061;
    2. 河北科技大学 信息科学与工程学院, 石家庄 050081;
    3. 河北经贸大学 管理科学与工程学院, 石家庄 050061
  • 作者简介:霍峥(1982-),女,河北邯郸人,讲师,博士,主要研究方向:隐私保护、移动对象数据库;张坤(1982-),女,河北石家庄人,讲师,博士,主要研究方向:数据挖掘;贺萍(1982-),女,山东莱阳人,讲师,博士,主要研究方向:无线传感器网络、图优化算法;武彦斌(1980-),男,河北石家庄人,教授,博士,主要研究方向:地理信息系统、位置大数据管理。
  • 基金资助:

Abstract: To solve the problem of privacy leakage in crowdsourced location data collection, a locally differentially private location data collection method with crowdsourcing was proposed. Firstly, a Voronoi diagram constructed by point-by-point insertion method was used to partition the road network space. Secondly, a random disturbance satisfying local differential privacy was used to disturb the original location data in each Voronoi grid. Thirdly, a designed spatial range query method was applied to noisy datasets to get the unbiased estimation of the actual result. Finally, experiments were carried out on spatial range queries to compare the proposed algorithm with PTDC (Privacy-preserving Trajectory Data Collection) algorithm. The results show that the query error rate is no more than 40%, and less than 20%in the best situation, and the running time is less than 8 seconds, which are better than those of PTDC algorithm while the proposed method has a higher degree of privacy preserving.

Key words: local differential privacy, road network, Voronoi grid, location data, moving object

摘要: 针对位置数据众包采集中个人位置隐私泄露的问题,提出了一种满足本地化差分隐私的位置数据众包采集方法。首先,使用逐点插入法构造维诺图,对路网空间进行分割;然后,采用满足本地化差分隐私的随机扰动的方式对每个维诺格中的位置数据进行扰动;再次,设计了一种在扰动数据集上进行空间范围查询的方法,获得对真实结果的无偏估计;最后,在空间范围查询下进行了实验验证,并与保护隐私的轨迹数据采集(PTDC)算法进行了对比,算法查询误差率最坏不超过40%,最好情况在20%以下,运行时间在8 s以内,在隐私保护度高于PTDC算法的前提下,上述参数优于PTDC算法。

关键词: 本地化差分隐私, 道路网络, 维诺格, 位置数据, 移动对象

CLC Number: