[发明专利]基于Voronoi多边形与Hilbert曲线编码的隐私保护查询方法

摘要

本发明涉及一种基于Voronoi多边形与Hilbert曲线编码的隐私保护查询方法，包括以下步骤：服务器端对目标对象所在平面进行Voronoi多边形划分，并利用Hilbert曲线进行划分编码，构建映射Hilbert单元格编码和Voronoi多边形的B+树索引；用户通过客户端向服务器提交自身位置p的Hilbert曲线编码值H(p)进行k近邻查询；服务器端在索引树上查找H(p)对应的Voronoi多边形C，生成C的最小外接矩形R；服务器端查找R的k‑1近邻Voronoi多边形，并将这些Voronoi多边形对应的Hilbert曲线编码值组成候选查询结果集合CaS，返回客户端；用户对CaS中的Hilbert曲线编码值进行解码，筛选出最近邻目标对象。实现保护位置隐私的k近邻查询。

主权项

一种基于Voronoi多边形与Hilbert曲线编码的隐私保护查询方法，其特征在于，所述查询方法如下，(1)存储有2‑维位置坐标集T的服务器对T所在平面S进行voronoi多边形划分，以集合T中所有POI点为对象构建S的Voronoi图；再设置Hilbert曲线参数N(Hilbert曲线阶数)和曲线填充起点Q(x0,y0)，利用Hilbert曲线对S进行填充编码，T集合中坐标点的Hilbert编码值为其所在的Hilbert单元区间的中心点的Hilbert值；构建关于Voronoi多边形与Hilbert曲线编码(阶数为N)映射关系的索引树HilVOR(T)；(2)用户在客户端输入其当前真实位置坐标p；客户端利用与服务器端相同的Hilbert曲线函数对p进行编码，采用与服务器端相同的Hilbert曲线填充起点Q(x0,y0)和曲线阶数N，计算得到编码值H(p)，并向服务器发起关于将H(p)的k近邻查询请求；(3)服务器端在索引树HilVOR(T)上查找H(p)所在的叶子节点leaf，leaf中存储的泰森多边形即为H(p)所在的主voronoi多边形C，计算C的最小外接矩形R；(4)设置剪枝距离阈值d，初始值为0；查找矩形R的所有k‑1近邻Voronoi多边形，即那些中心点与C的中心点的距离跳数不超过k‑1的Voronoi多边形，对k‑1近邻Voronoi多边形C’，计算C’的中心距离矩形R顶点的最远距离dmax(C,C’)，若dmax(C,C’)>d，则替换剪枝距离当前值，即d＝dmax(C,C’)；否则，C’对应POI的Hilbert曲线编码加入候选集CaS；(5)服务器端将查询结果CaS，返回查询客户端；(6)客户端对返回的集合CaS中的Hilbert曲线编码值根据参数Q(x0,y0)和N进行解码，获取Hilbert编码值所对应二维点的坐标P(x,y)，根据自身位置p，从CaS中查找与p欧氏距离最小的K个近邻位置坐标，即目标查询结果。