Crowdsourcing location data collection for local differential privacy

doi:10.11772/j.issn.1001-9081.2018071541

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 Zheng¹, ZHANG Kun², HE Ping¹, WU Yanbin³

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. 河北经贸大学信息技术学院, 石家庄 050061;
2. 河北科技大学信息科学与工程学院, 石家庄 050081;
3. 河北经贸大学管理科学与工程学院, 石家庄 050061

作者简介:霍峥(1982-),女,河北邯郸人,讲师,博士,主要研究方向:隐私保护、移动对象数据库;张坤(1982-),女,河北石家庄人,讲师,博士,主要研究方向:数据挖掘;贺萍(1982-),女,山东莱阳人,讲师,博士,主要研究方向:无线传感器网络、图优化算法;武彦斌(1980-),男,河北石家庄人,教授,博士,主要研究方向:地理信息系统、位置大数据管理。
基金资助:
国家自然科学基金资助项目（61502279）；河北省自然科学基金资助项目（F2018210109）；河北省高等学校科学研究项目（ZD2018205，QN2018116）。

Abstract

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:

TP311.13

HUO Zheng, ZHANG Kun, HE Ping, WU Yanbin. Crowdsourcing location data collection for local differential privacy[J]. Journal of Computer Applications, 2019, 39(3): 763-768.

霍峥, 张坤, 贺萍, 武彦斌. 满足本地化差分隐私的众包位置数据采集[J]. 计算机应用, 2019, 39(3): 763-768.

References

[1] 黄毅,霍峥,孟小峰.CoPrivacy:一种用户协作无匿名区域的位置隐私保护方法[J].计算机学报,2011,34(10):1976-1985.(HUANG Y, HUO Z, MENG X F. CoPrivacy:a collaborative location privacy-preserving method without cloak region[J]. Chinese Journal of Computers, 2011, 34(10):1976-1985.)
[2] SEI Y, OHSUGA A. An algorithm for privacy-preserving location data collection by probabilistic dummy generation[J]. IEEE Transactions on Electronics Information and Systems, 2015, 135(6):660-670.
[3] ZHANG L, ZHANG W. Generalization-based privacy-preserving data collection[C]//Proceedings of the 2008 International Conference on Data Warehousing and Knowledge Discovery. Berlin:Springer, 2008:115-124.
[4] HIGUCHI T, MARTIN P, CHAKRABORTY S, et al. AnonyCast:privacy-preserving location distribution for anonymous crowd tracking systems[C]//UbiComp'15:Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York:ACM, 2015:1119-1130.
[5] GIDOFALVI G, HUANG X, PEDERSEN T B. Privacy:preserving trajectory collection[C]//GIS'08:Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2008:Article No. 46.
[6] NGUYEN T T, XIAO X, YANG Y, et al. Collecting and analyzing data from smart device users with local differential privacy[EB/OL].[2018-06-19]. https://arxiv.org/pdf/1606.05053.pdf.
[7] QIN Z, YANG Y, YU T, et al. Heavy hitter estimation over set-valued data with local differential privacy[C]//CCS'16:Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM, 2016:192-203.
[8] TO H, GHINITA G, SHAHABI C. A framework for protecting worker location privacy in spatial crowdsourcing[J]. Proceedings of the VLDB Endowment, 2014, 7(10):919-930.
[9] CHEN R, LI H, QIN A K, et al. Private spatial data aggregation in the local setting[C]//Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Washington DC:IEEE Computer Society, 2016:289-300.
[10] DWORK C. Differential privacy[C]//ICALP'06:Proceedings of the 33rd International Conference on Automata, Languages and Programming. Berlin:Springer, 2006:1-12.
[11] DWORK C, LEI J. Differential privacy and robust statistics[C]//STOC'09:Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York:ACM, 2009:371-380.
[12] XIONG S, SARWATE A D, MANDAYAM N B. Randomized requantization with local differential privacy[C]//Proceedings of 2016 IEEE International Conference on Acoustics. Washington, DC:IEEE Computer Society. 2016:2189-2193.
[13] WARNER S L. Randomized response:a survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965, 60(309):63-69.
[14] PAN X, WU L, HU Z, et al. Voronoi-based spatial cloaking algorithm over road network[C]//Proceedings of the 2014 International Conference on Database and Expert Systems Applications. Berlin:Springer, 2014:273-280.
[15] 霍峥,王卫红,曹玉辉.PTDC:路网环境中感知隐私的轨迹数据采集技术[J].计算机应用,2017:37(9):2567-2571.(HUO Z, WANG W H, CAO Y H. PTDC:privacy-aware trajectory data collection technology under road network constraint[J]. Journal of Computer Applications, 2017, 37(9):2567-2571.)

Crowdsourcing location data collection for local differential privacy

满足本地化差分隐私的众包位置数据采集

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Zhuo, SONG Zihui, SHEN Xin, CHEN Xin. Local differential privacy protection mechanism for mobile crowd sensing with edge computing [J]. Journal of Computer Applications, 2021, 41(9): 2678-2686.
[2]	Yusheng HU, Bingwei HE, Qingkang DENG. Moving object detection and static map reconstruction with hybrid vision system [J]. Journal of Computer Applications, 2021, 41(11): 3332-3336.
[3]	ZHAO Guanghua, LAI Jianhui, CHEN Yanyan, SUN Haodong, ZHANG Ye. Residents' travel origin and destination identification method based on naive Bayes classification [J]. Journal of Computer Applications, 2020, 40(1): 36-42.
[4]	FU Yu, WANG Hong. Virtual trajectory filling algorithm for location privacy protection [J]. Journal of Computer Applications, 2019, 39(8): 2318-2325.
[5]	MA Fangfang, LIU Shubo, XIONG Xingxing, NIU Xiaoguang. Privacy protection based on local differential privacy for numerical sensitive data of wearable devices [J]. Journal of Computer Applications, 2019, 39(7): 1985-1990.
[6]	FENG Jun, LI Dingsheng, LU Jiamin, ZHANG Lixia. Spatio-temporal index method for moving objects in road network based on HBase [J]. Journal of Computer Applications, 2018, 38(6): 1575-1583.
[7]	LI Jiajia, LIU Xiaojing, LIU Xiangyu, XIA Xiufeng, ZHU Rui. Improved time dependent fast travel time algorithm by dynamically selecting heuristic values [J]. Journal of Computer Applications, 2018, 38(1): 120-125.
[8]	HUO Zheng, CUI Honglei, HE Ping. k-CS algorithm: trajectory data privacy-preserving based on semantic location protection [J]. Journal of Computer Applications, 2018, 38(1): 182-187.
[9]	HUO Zheng, WANG Weihong, CAO Yuhui. PTDC:privacy-aware trajectory data collection technology under road network constraint [J]. Journal of Computer Applications, 2017, 37(9): 2567-2571.
[10]	XU Wei, LI Wengen, ZHANG Yichao, GUAN Jihong. Probabilistic bichromatic reverse-kNN query on road network [J]. Journal of Computer Applications, 2017, 37(2): 341-346.
[11]	LYU Shaoqian, MENG Fanrong, YUAN Guan. Trajectory structure-based moving object hotspots discovery [J]. Journal of Computer Applications, 2017, 37(1): 54-59.
[12]	HE Wei, QI Qi, ZHANG Guoyun, WU Jianhui. Moving object detection method based on multi-information dynamic fusion [J]. Journal of Computer Applications, 2016, 36(8): 2306-2310.
[13]	GAO Zhiyong, TANG Wenfeng, HE Liangjie. Moving object detection with moving camera based on motion saliency [J]. Journal of Computer Applications, 2016, 36(6): 1692-1698.
[14]	ZHOU Sha, WANG Run, ZHEN Wenjie. Pedestrian route choice model considering subjective judgment delay [J]. Journal of Computer Applications, 2016, 36(4): 1146-1150.
[15]	SONG Lujie, MENG Fanrong, YUAN Guan. Moving object location prediction algorithm based on Markov model and trajectory similarity [J]. Journal of Computer Applications, 2016, 36(1): 39-43.