不规则线段树的差分隐私位置隐私保护方法

胡德敏，廖正佳

(上海理工大学 光电信息与计算机工程学院，上海 200093)

1 引 言

差分隐私[1]作为位置扰动中一个常用的方法，具有严格的推理和证明的隐私保证，攻击者无论是否拥有背景知识[2]都无法推断出一条真实的位置数据，日渐成为位置保护中最受欢迎的方法.

基于差分隐私的位置保护方法会牺牲数据效用，用户在移动环境下连续查询时，单个位置点或兴趣点添加噪声后，会出现噪声叠加导致位置查询精度和服务质量下降等问题.树形结构的差分隐私[3,12]方法能拆分位置数据集以增强数据效用，并能在保护位置隐私的同时有效提高移动查询精度.但规则树形结构的差分隐私方法会造成大量无效零节点，数据结构过大，在查询精度上还有进一步提高的空间.

因此在规则树结构的差分隐私位置保护的基础上，提出了不规则树结构的差分隐私位置保护方法(Irregular Segment Tree Differential Privacy，ISTDP).该方法能有效解决差分隐私方法在移动环境下的连续查询精度下降的问题，并能适应不同密度环境.将k-匿名机制[4]与差分隐私相结合，引入线段树(Segment Tree)[5]的概念，形成匿名集后，使用不规则的线段树结构对数据进行划分；并将不规则线段树中节点覆盖率的差异加入对查询精度的考量，推导出衡量最优不规则线段树的估值函数；根据节点覆盖率构造子树的估值函数，从而得出较低的查询误差的线段树作为最终的不规则线段树；最后为每个节点分配具有较小误……