基于本地化差分隐私的空间数据近似k-近邻查询

作者：张啸剑; 徐雅鑫; 孟小峰

来源：计算机研究与发展, 2022, 59(07): 1610-1624.

• 本地化差分隐私
• k-近邻查询
• 局部敏感Hash
• 隐私预算分割
• 用户分组

针对现有本地编码机制与本地扰动机制在收集空间数据时不具有保距性的问题，提出了基于局部敏感Hash结构(locality-sensitive hashing, LSH)的近似k-近邻(k nearest neighbor,kNN)查询算法PELSH与PULSH.这2种算法利用具有多Hash函数的多Hash表对所有用户位置数据进行索引，结合多Hash表结构响应近似kNN查询.每个用户结合收集者所共享的多Hash表副本，将自身位置数据以汉明空间嵌入方式编码成0/1串.借助LSH结构对0/1串进行Hash压缩，并利用GRR机制与按位扰动机制对压缩后的0/1串进行本地处理.收集者利用每个用户的报告值重构多Hash表索引结构，遍历多Hash表响应空间近似kNN查询.为了有效地利用LSH索引结构的特点，PELSH和PULSH算法结合隐私预算分割与用户分组策略来重构多Hash表结构，基于这2种策略设计了4种本地扰动算法PELSHB,PELSHG,PULSHB和PULSHG.PELSH和PULSH算法与现有的近似kNN查询算法在真实的大规模空间数据集上的实验结果表明，所设计的近似空间kNN查询效果优于同类算法.

• 单位
  河南财经政法大学; 中国人民大学