基于自适应网格的隐私空间分割方法

基于网格与差分隐私保护的空间数据分割得到了研究者的广泛关注,空间数据的大小、数据的偏斜性以及拉普拉斯噪音的多少直接制约着空间分割的精度.针对现有基于网格分割方法难以有效兼顾大规模空间数据、数据偏斜性与噪音量的不足,提出了一种基于伯努利随机抽样技术的3层自适应网格分割(sampling-based three-layer adaptive grid decomposition,STAG)方法,该方法利用满足差分隐私的抽样技术抽取空间数据点作为分割对象.根据查询粒度的不同,首先在中间层利用指数机制与高通滤波过滤掉小于阈值的网格单元,然后利用Down-Split方法继续细分大于阈值的网格单元.对于那些小于阈值且连接的单元格,利用Up-Merge操作对这些单元进行最优化重组,形成粗粒度的网格单元.STAG与UG(uniform grid),AG(adaptive grid),Kd-Stand(kd-tree-based standard method),KdHybrid(kd-tree-based hybrid method)在真实的大规模空间数据集上实验结果表明:其分割精度以及响应范围查询效果优于同类算法.

KD-TSS:精确隐私空间分割方法

基于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在真实的大规模空间数据集上实验结果表明,其分割精度以及响应范围查询效果优于同类算法。