Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy（2007）理解与总结

背景问题

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和可信第三方有）

Q：

1. Hilbert Curve 理论基础？