背景问题
NN query：Nearest Neighbor query。
用户需要找离自己最近的某些点，但是同时自己的准确位置不能泄露。
之前研究的不足
传统加密技术有O（n）的计算开销，log级的通信开销。
未开发节点的空间特性。
本文贡献
1. 用Hilbert曲线，将原始空间（2D）转换为编码后的空间，存在服务器中，计算复杂度降为（得到的结果是近似值）
K是前K个最近点，N是Hilbert变换空间的维数
通信复杂度降为O(K)
2. 两种位置隐私metric（比k-anonymity好）：
user-based anonymity 叫 u-anonymity：混淆发请求user的身份
M是总user数
area-based anonymity 叫 a-anonymity：混淆发送请求的user点的位置
A是所有点的全集
相当于对于user和area，都加大了混淆的范围，把局部混淆扩展到全局混淆。
原理
结果集混淆：
混淆所有感兴趣点
KNN盲估：满足上述三个混淆的KNN请求。
单向（one-way）转换，在转换后的空间处理请求。
要实现上述转换，会有精度损失。
两个度量转换结果好坏的自定义参数：
与原空间相同结果所占比
此公式有改进空间
Hilbert转换： 每个点通过转换，都会有一个H-value（相当于把二维映射到一维），H-value可能会有重复相同的。
空间加密技术，key为
其实点坐标（2维），方向角，，曲线规格系数
线下空间加密：对POI（point of interest），即查询的目标点，进行空间编码（每个点转换出对应的H-value）。
升序存放POI的H-value
线上请求处理：请求在意转换的空间被处理，然后解码得到原始目标点。
计算发出请求的user的H-value
找离user的H-value最近的K个点，再自解码，即得解。
以上方法仅用单Hilbert曲线，单Hilbert曲线的2个缺点：
1. 有的点之间欧拉距离近，但是H-value值可能差很多，比如起点和终点（在第一级Hilbert曲线中）
2. 近似解集和最优解集，最多会有一半的点不同。
双Hilbert曲线方法：
原始空间O，经过Hilbert变换为A，A旋转90度为B（A、B对应不同的SDK）。A、B分别算自己的KNN，然后得到2K个点，解码后通过欧拉距离，取最短的K个点为解。
位置查询也可扩展为Text相关的内容。
实际使用结构（标题blind在于发送的东西都不含真实信息，且Key只有user和可信第三方有）
网友评论