基于本地差分隐私的空间数据自适应划分算法

空间位置数据分布通常具有不均匀性,不同位置区域的密度差异较大,在本地差分隐私模型中无法直接获取用户真实的位置数据,使得空间位置划分方法受到限制以及数据发布存在查询精度低、通信代价大等问题。为在本地差分隐私模型下的大规模空间数据采集和发布过程中进行空间划分,提出一种空间数据分层自适应划分算法KDG-HT。通过收集部分用户的数据来初步获取区域的分布情况,采用KD-树的思想划分区域,并利用抽样技术对用户进行分组,根据分组用户统计结果所提供的先验知识来完成多层细粒度划分。在此基础上,结合差分隐私模型的并行组合特性分层扰动用户数据,从总体上实现发布数据的ε-差分隐私保护。实验结果表明,KDG-HT算法适用于具有不同数据分布情况的大规模空间数据集,查询精度及运行效率优于RAPPOR、UG、GT-R等算法,其中与GT-R算法相比,KDG-HT算法发布数据的查询精度最高提升3倍,运行效率提高17%。