基于<i>k</i>-泛化技术的时空数据个人隐私保护方法

杨姿; 宁博; 李毅

doi:10.3969/j.issn.1000-5641.2017.05.016

基于k-泛化技术的时空数据个人隐私保护方法

doi: 10.3969/j.issn.1000-5641.2017.05.016

大连海事大学信息科学技术学院, 辽宁大连 116026

基金项目:

国家自然科学基金广东联合基金重点项目 U1401256

辽宁省自然科学基金 201602094

详细信息

作者简介:
杨姿, 女, 硕士研究生, 研究方向为时空数据隐私保护.E-mail:winni103@vip.qq.com

通讯作者:
宁博, 男, 副教授, 硕士生导师, 研究方向为数据管理, 隐私保护.E-mail:ningbo@dlmu.edu.cn

中图分类号: TP391
计量
- 文章访问数: 141
- HTML全文浏览量: 141
- PDF下载量: 266
- 被引次数: 0
出版历程
- 收稿日期: 2017-06-20
- 刊出日期: 2017-09-25

Privacy preserving method of spatio-temporal data based on k-generalization technology

College of Information Science and Technology, Dalian Maritime University, Dalian Liaoning 116026, China

摘要

摘要: 近些年来，基于位置系统的设备越来越多，从而导致用户的大量位置信息被移动设备获取并利用，从数据挖掘的角度来说，这些数据具有不可估量的价值，但从个人隐私方面来说却恰恰相反，每个人都不希望自己的信息被泄露和利用，从而引发了人们强烈的隐私关注.目前许多文献都提出了隐私保护技术来解决这个问题，概括来说是干扰、抑制和泛化几大类.为了对个人时空数据的隐私进行保护，本文提出了k-泛化的方法.对用户可能出现的点进行范围限定，更好地提高了数据的可用性；对泛化节点的选取要使得用户的安全性最高；考虑了多个敏感节点存在情况下的解决方案，并且出于提高数据效用的目的对多个敏感节点进行了优化.最后通过实验评估了算法的性能并且验证了算法保护个人隐私是有效的.
- 隐私 /
- 时空数据 /
- 匿名 /
- 泛化
Abstract: In recent years, more and more devices based on location system, resulting in a large amount of location information by the mobile device users to access and use, from the perspective of data mining, the data is of immeasurable value, but in terms of personal privacy, people don't want their information to be leaked and used to sparked strong privacy concerns. At present, many papers have proposed privacy protection technology to solve this problem. Generally speaking, there are several categories of interference, suppression and generalization. In order to protect the privacy of personal spatio-temporal data, this paper proposes a method of k-generalization. To limit the scope of the user may appear, improve the availability of data; selection of nodes to generalization so that the user's maximum security; considers multiple sensitive node solutions exist under the condition, and for the purpose of improving the data utility on a number of sensitive nodes are optimized. Finally, the performance of the algorithm is evaluated by experiments, and it is proved that the algorithm is effective to protect personal privacy.
- privacy /
- spatio-temporal data /
- anonymous /
- generalization

HTML全文

图 1 用户轨迹图

Fig. 1 Graph of user trajectory

下载: 全尺寸图片幻灯片

图 2 相似轨迹集图例

Fig. 2 Similar trajectory set example

下载: 全尺寸图片幻灯片

图 3 只有一个点的泛化区域

Fig. 3 Generalization region $g_{1}$ with just one vertex

下载: 全尺寸图片幻灯片

图 4 有两个点的泛化区域 $g_1$

Fig. 4 Generalization region $g_{1}$ with two nodes

下载: 全尺寸图片幻灯片

图 5 最终的泛化区域 $g_{1}$

Fig. 5 Final generalization region $g_{1}$

下载: 全尺寸图片幻灯片

图 6 参数 $k$ 对平均泛化区域大小的影响

Fig. 6 Average generalization area size for the parameters $k$ limit

下载: 全尺寸图片幻灯片

图 7 参数 $k$ 对运行时间的影响

Fig. 7 Time performance for the parameters $k $ limit

下载: 全尺寸图片幻灯片

图 8 参数 $k$ 对泛化率的影响

Fig. 8 Generalization ratio for the parameters $ k $ limit

下载: 全尺寸图片幻灯片

图 9 敏感节点 $n$ 的个数对平均泛化区域的影响

Fig. 9 The influence of the number of sensitive nodes n on the average generalization region

下载: 全尺寸图片幻灯片

表 1 用户轨迹数据表

Tab. 1 User trajectory data table

用户$i$	时间t
用户$i$	T$_{1}$	T$_{2}$	T$_{3}$	T$_{4}$	T$_{5}$	T$_{6}$	T$_{7}$	T$_{8}$	T$_{9}$
U$_{1}$	2	3	4	6	0	0	7	0	0
U$_{2}$	1	2	3	4	0	6	5	0	7
U$_{3}$	2	3	0	5	0	0	0	7	0
U$_{4}$	1	2	3	0	4	6	7	8	9
U$_{5}$	8	7	5	0	0	3	2	0	0

下载: 导出CSV

表表 1 参数估计模拟结果

Tab. 表 1 Simulation results of parametric estimation

算法1匿名化算法
Input:隐私值k, 轨迹数据集DS, 敏感节点集S, 速度v
Output:地图M*
1: Set DS=getSet(数据集);
2: Map M=creatGraph(DS);
3: G=null;
4: for all v$_{i}\in $ S & & v$_{i}$ isNotGeneralized;
5: creat group g;
6: g.add(v$_{i})$;
7: while(p＞k){
8: t=用户在敏感节点停留的时间;
9: r=v*t;
10: Close Area=$\pi $r$^{2}$;
11: if(方向一致){
12: if ((v$_{i} \in $Close Area) & & $\exists (＜$g, v$_{i}$, p$＞))${
13: candidateSet.add(v$_{i})$; }
14: if(v$_{i}\in $S & & (v$_{i} \in $Close Area) & & $\exists (＜$g, v$_{i}$, p$＞))${
15: g.add(v$_{i})$;
16: }else {
17: for (int i=0;i$＜$candidateSet.lenth-2;i++) {
18: p$^{-}$=1/(Similar Trajectory Set (g, candidateSet[i]));
19: p$^{+}$=1/(Similar Trajectory Set (g, condidateSet[i]+1));
20: pr=p$^{-}$/p$^{+}$
21: if(pr$＜$1){
22: fNode=condidateSet[i];
23: p=p$^{-}$;
24: Eq=Similar Trajectory Set(g, candidateSet[i]));
25: }else{
26: fNode = condidateSet[i+1];
27: p=p$^{+}$;
28: Eq=Similar Trajectory Set(g, candidateSet[i])); }
29: g.add(fNode);
30: G.add(g, Eq); }}
31: }
32: M$^{\ast}$=anonymizeMap(M, G);
33: Return M$^{\ast }$;

下载: 导出CSV

参考文献(20)

[1]	XIAO Y, XIONG L. Protecting Locations with Differential Privacy under Temporal Correlations[C]//The ACM Sigsac Conference on Computer and Communications Security. New York:ACM, 2014:1298-1309.
[2]	GEDIK B, LIU L. Protecting location privacy with personalized k-anonymity:Architecture and algorithms[J]. IEEE Transactions on Mobile Computing, 2008, 7(1):1-18. doi: 10.1109/TMC.2007.1062
[3]	CICEK A E, NERGIZ M E, SAYGIN Y. Ensuring location diversity in privacy-preserving spatio-temporal data publishing[J]. The VLDB Journal, 2014, 23(4):609-625. doi: 10.1007/s00778-013-0342-x
[4]	HUNDEPOOL A J, WILLENBORG L C R J. Mu-and tau-argus:Software for statistical disclosure control[J].
[5]	SAMARATI P. Protecting respondent's identities in microdata release[J]. IEEE Trans Knowl Data Eng, 2001, 13(6):1010-1027. doi: 10.1109/69.971193
[6]	YU T, JAJODIA S. Secure Data Management in Decentralized Systems[M]. New York:Springer, 2007.
[7]	田秀霞, 王晓玲, 高明, 等.数据库服务-安全与隐私保护[J].软件学报, 2010(5):991-1006. http://www.cnki.com.cn/Article/CJFDTOTAL-DNBC201416054.htm
[8]	ABUL O, BONCHI F, NANNI M. Never Walk Alone:Uncertainty for Anonymity in Moving Objects Databases[C]//IEEE, International Conference on Data Engineering.[S.l.]:IEEE Computer Society, 2008:376-385.
[9]	ATZORI M, ATZORI M, SAYGIN Y. Towards trajectory anonymization:A generalization-based approach[C]//Sigspatial ACM Gis 2008 International Workshop on Security and Privacy in Gis and Lbs. New York:ACM, 2008:52-61.
[10]	SWEENEY L. K-anonymity:A model for protecting privacy[J]. International Journal on Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5):557-570. doi: 10.1142/S0218488502001648
[11]	MACHANAVAJJHALA A, KIFER D, GEHRKE J. L -diversity:Privacy beyond k -anonymity[J]. Acm Transactions on Knowledge Discovery from Data, 2007, 1(1):3. doi: 10.1145/1217299
[12]	LI N H, LI T C, VENKATASUBRAMANIAN S. t-Closeness:Privacy Beyond k-Anonymity and l-Diversity[C]//IEEE, International Conference on Data Engineering.[S.l.]:IEEE, 2007:106-115.
[13]	MAO J, SONG Q, JIN C, et al. TSCluWin:Trajectory Stream Clustering over Sliding Window[M]//Database Systems for Advanced Applications. US:Springer, 2016.
[14]	ZHANG Z, WANG Y, MAO J, et al. DT-KST:Distributed top-k similarity query on big trajectory streams[J]. 2017:199-214.
[15]	WU W, XIAO Y, WANG W, et al. k-symmetry model for identity anonymization in social networks[C]//EDBT 2010, International Conference on Extending Database Technology. Switzerland:DBLP, 2010:111-122.
[16]	DWORK C. Differential privacy[J]. Lecture Notes in Computer Science, 2006, 4052(2):1-12.
[17]	KELLARIS G, PAPADOPOULOS S, XIAO X, et al. Differentially private event sequences over infinite streams[J]. Proceedings of the Vldb Endowment, 2014, 7(12):1155-1166. doi: 10.14778/2732977
[18]	CHEN R, FUNG B C M, DESAI B C, et al. Differentially private transit data publication:a case study on the montreal transportation system[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2012:213-221.
[19]	CAO Y, YOSHIKAWA M. Differentially private real-time data release over infinite trajectory streams[C]//IEEE International Conference on Mobile Data Management.[S.l.]:IEEE, 2015:68-73.
[20]	MIGUEL E ANDRÉS, NICOLAS E BORDENABE, LONSTANTINOS Chatzikokolakis, et al. Geo-indistinguishability:Differential privacy for location-based systems[C]//Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications security. New York:ACM, 2013:901-914.