[發明專利]基于Voronoi多邊形與Hilbert曲線編碼的隱私保護查詢方法

有效

• 申請號: 201710326035.8
• 申請日: 2017-05-10
• 公開（公告）號: CN107169372B
• 公開（公告）日: 2020-04-14
• 發明（設計）人: 倪巍偉;陸介平;胡磊;李靈奇
• 申請（專利權）人: 東南大學
• 主分類號: G06F21/62
• 分類號: G06F21/62;G06F16/2458
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 杜靜靜

1.一種基于Voronoi多邊形與Hilbert曲線編碼的隱私保護查詢方法，其特征在于，所述查詢方法如下，

步驟(1)存儲有2-維位置坐標集T的服務器對T所在平面S進行voronoi多邊形劃分，以集合T中所有POI點為對象構建S的Voronoi圖；再設置Hilbert曲線參數N即Hilbert曲線階數和曲線填充起點Q(x₀,y₀)，利用Hilbert曲線對S進行填充編碼，T集合中坐標點的Hilbert編碼值為其所在的Hilbert單元區間的中心點的Hilbert值；構建關于Voronoi多邊形與Hilbert曲線編碼即階數為N映射關系的索引樹HilVOR(T)；

步驟(2)用戶在客戶端輸入其當前真實位置坐標p；客戶端利用與服務器端相同的Hilbert曲線函數對p進行編碼，采用與服務器端相同的Hilbert曲線填充起點Q(x₀,y₀)和曲線階數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(x₀,y₀)和N進行解碼，獲取Hilbert編碼值所對應二維點的坐標P(x,y)，根據自身位置p，從CaS中查找與p歐氏距離最小的K個近鄰位置坐標，即目標查詢結果；

所述步驟(1)中構建關于Voronoi多邊形與Hilbert曲線編碼(階數為N)映射關系的索引樹HilVOR(T)，具體如下，

索引樹生成方法如下：

①生成空B+樹bptree；

②按Hilbert曲線編碼值遞增的順序，對每個編碼值h_i執行步驟③和④；

③查詢Hilbert曲線編碼值h_i對應位置的最近鄰Voronoi多邊形的中心點q；

④如果h_i對應的Voronoi多邊形與上一個Hilbert曲線編碼值h_i-1的最近鄰Voronoi多邊形不同，則將h_i,q即h_i為key，q為value作為葉節點插入到bptree中。

2.根據權利要求1所述的Voronoi多邊形與Hilbert曲線編碼的隱私保護查詢方法，其特征在于，所述2-維位置坐標集T為服務器數據空間S中所有數據對象的集合；真實位置p位于數據空間S中；H(p)的主Voronoi多邊形C指H(p)對應的Hilbert單元格位于C中；兩個位置點間的距離跳數指連接兩點的直線段跨越的Voronoi多邊形的個數。