基于本地差分隐私的空间范围查询方法

张啸剑 付 楠 孟小峰

1(河南财经政法大学计算机与信息工程学院 郑州 450002) 2(中国人民大学信息学院 北京 100872)

信息时代的飞速发展，用户空间数据(例如移动用户位置、GPS位置、家庭住址等)的收集与分析能够改善IT企业的软件与服务质量，以及向用户提供更好的个性化体验.然而，不可信第三方对空间数据进行收集与分析时，个人的敏感信息有可能被泄露.例如不可信销售网站通过收集客户的位置信息，可以学习出客户的购物行为模式以及家庭住址.因此，在此情景下，用户通常无法掌控自己的空间隐私数据.本地差分隐私保护技术[1]的出现使得用户可以自己扰动自身数据之后再响应收集者的需求.目前基于本地差分隐私着眼于频率估计、均值估计等研究，而涉及空间范围查询的工作却很少.基于空间数据的范围查询是空间数据分析常用的技术之一.例如图1表示100万条纽约出租车位置数据(New York City data, NYC)散点图，查询框Q1要求返回曼哈顿医院附近范围内的乘客数量.该查询对应的SQL语句可以表示为Q1:Select Count(*) from NYC where -14≤lat≤23 and -10≤lon≤20.

Fig. 1 Spatial range queries on NYC图1 基于NYC的空间范围查询

在Q1查询中，用户位置所对应的经纬度为敏感信息.因此，用户在共享自身位置之前，需要本地化差分隐私保护处理.而在此过程中存在诸多挑战：1)收集者如何构建高效的空间索引结构收集用户的报告数据；2)由于空间数据的值域通常很大，用户采用什么样的编码机制与扰动机制处理自身的空间数据；3)如何设计高效的后置……