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

有效

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

本發明涉及一種基于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曲線編碼的隱私保護查詢方法，屬于數據查詢技術領域。

背景技術

近年來，基于位置信息的服務在計算機應用領域得到了廣泛的應用，例如GPS導航、空間信息查詢等。這類應用多數基于k近鄰查詢，其模式為服務提供方在服務器上存儲所有用戶感興趣對象的信息(包括位置信息)，用戶配置能夠獲取用戶所在地點位置信息(2維經緯度坐標)的設備(例如GPS終端)，通過向服務提供方發送用戶當前位置，服務器方返回距用戶當前位置最近的k個對象的相關信息。這種模式要求用戶必須向服務提供方發送其真實位置信息，隨著用戶對個體隱私數據的日益關注，出現了用戶在不泄漏自身位置信息情況下獲得k近鄰查詢服務的應用需求，保護位置隱私的k近鄰查詢成為數據庫與信息安全研究的一個熱點。用戶不泄漏自身位置信息主要表現在兩方面：(1)用戶無需向服務提供方發送其真實位置信息；(2)攻擊者(不可信方)能夠推測出的用戶可能位置的可能性滿足用戶關于保護自己位置隱私的要求。

已有的一些技術和方法多數采用依賴可信第三方(在線或離線模式)輔助實現保護位置隱私的k近鄰查詢，例如：cloaking技術：用戶將真實位置及對最小逆推區域面積的要求發送到可信第三方，可信第三方為每個用戶生成包含其位置的矩形區域，并將矩形發送到服務器方，服務器方返回到矩形內點的所有可能k近鄰，可信第三方篩選出真實結果，返回客戶端；基于數據變換技術往往依賴于離線第三方將數據和查詢轉變到一個新的數據空間以保護用戶的位置隱私信息。基于位置梗阻的方法，無需可信第三方參與，采用客戶端發送假位置，服務器不斷發送到假位置的近鄰點供客戶端檢測，直到客戶端找到滿足用戶要求的k個近鄰對象為止，但該方法存在查詢迭代過程不可控問題，與多數隱私保護查詢方法一樣，存在查詢處理效率低的問題。

在保護用戶位置隱私查詢研究領域，為了保護查詢者位置隱私不泄露，需要對查詢者的準確位置進行模糊化處理，通過服務器和查詢客戶端的特殊處理與交互機制，實現位置隱私和查詢結果準確性的兼顧，這種兼顧往往以查詢性能的損失為代價。因此，提升查詢性能是保護位置隱私查詢需要解決的重要問題。

Voronoi圖為查詢k近鄰提供了一種快速的方式，每個Voronoi多邊形區域內所有點的最近鄰POI就是其Voronoi多邊形的中心點，根據Voronoi多邊形的鄰接多邊形可以很快地查找到某個POI的K近鄰Voronoi多邊形，在服務器端構建Voronoi多邊形的索引可以有效提高服務器端查詢目標對象K近鄰的效率。

發明內容

本發明正是針對現有技術中存在的技術問題，提供一種基于Voronoi多邊形與Hilbert曲線編碼的隱私保護查詢方法，

為了實現上述目的，本發明的技術方案如下，一種基于Voronoi多邊形與Hilbert曲線編碼的隱私保護查詢方法，其特征在于，所述查詢方法如下，