文献类型：期刊文献

中文题名：KD-TSS:精确隐私空间分割方法

英文题名：KD-TSS: Accurate Method for Private Spatial Decomposition

作者：金凯忠[1];张啸剑[1];彭慧丽[1,2]

第一作者：金凯忠

机构：[1]河南财经政法大学计算机与信息工程学院;[2]河南广播电视大学

第一机构：河南财经政法大学计算机与信息工程学院

年份：2017

卷号：11

期号：10

起止页码：1579-1590

中文期刊名：计算机科学与探索

外文期刊名：Journal of Frontiers of Computer Science and Technology

收录：北大核心:【北大核心2014】；CSCD:【CSCD2017_2018】；

基金：国家自然科学基金No.61502146;河南省科技攻关项目No.162102310411;河南省教育厅高等学校重点科研项目No.16A520002;河南省高等学校青年骨干教师项目No.2013GGJS-098;河南财经政法大学青年拔尖人才资助计划;郑州市科技局普通科技攻关项目No.153PKJGG115~~

语种：中文

中文关键词：差分隐私;KD-树;隐私空间划分;伯努利随机抽样;稀疏向量技术

外文关键词：differential privacy; KD-Tree; private spatial decomposition; Bernoulli random sampling; sparse vector technology

摘要：基于KD-树与差分隐私保护的空间数据分割得到了研究者的广泛关注,空间数据的大小与拉普拉斯噪音的多少直接制约着空间分割的精度。针对现有基于KD-树分割方法难以有效兼顾大规模空间数据与噪音量不足的问题,提出了一种满足差分隐私的KD-树分割方法 SKD-Tree(sampling-based KD-Tree)。该方法利用满足差分隐私的伯努利随机抽样技术,抽取空间样本作为分割对象,然而却没有摆脱利用树高度控制拉普拉斯噪音。启发式设定合适的树高度非常困难,树高度过大,导致结点的噪音值过大;树高度过小,导致空间分割粒度太粗劣。为了弥补SKD-Tree方法的不足,提出了一种基于稀疏向量技术(sparse vector technology,SVT)的空间分割方法 KD-TSS(KD-Tree with sampling and SVT)。该方法通过SVT判断树中结点是否继续分割,不再依赖KD-树高度来控制结点中的噪音值。SKD-Tree、KD-TSS与KD-Stand、KD-Hybrid在真实的大规模空间数据集上实验结果表明,其分割精度以及响应范围查询效果优于同类算法。
KD-Tree-based differentially private spatial decomposition has attracted considerable research attention in recent years.The trade-off between the size of spatial data and Laplace noise directly constrains the accuracy of decomposition.This paper proposes a straightforward method with differential privacy,called SKD-TS(samplingbased KD-Tree)to partition spatial data.To handle the large-scale spatial data,this method employs Bernoulli random sampling technology to obtain the samples.While SKD-Tree still relies on the height of KD-Tree to control the Laplace noise.However,the choice of the height is a serious subtitle:a large height makes excessive noise in the nodes,while a small height leads to the partition too coarse-grained.To remedy the deficiency of SKD-Tree,this paper proposes another method,called KD-TSS(KD-Tree with sampling and SVT)for spatial decomposition.The sparse vector technology(SVT)is used in KD-TSS to judge whether a node of KD-Tree should be split,without depending on the height.SKD-TS and KD-TSS methods are compared with existing methods such as KD-Stand,KD-Hybird on the large-scale real datasets.The experimental results show that the two algorithms outperform their competitors,achieve the accurate decomposition and results of range query.