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

Abstract: 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 (sampling-based 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.

Key words: differential privacy, KD-Tree, private spatial decomposition, Bernoulli random sampling, sparse vector technology