基于本地化差分隱私的空間數據近似k-近鄰查詢

張嘯劍 徐雅鑫 孟小峰

1(河南財經政法大學計算機與信息工程學院 鄭州 450002) 2(中國人民大學信息學院 北京 100872)

人工智能與大數據技術的迅猛發展，使得個人空間數據(例如移動用戶位置、GPS位置、家庭住址等)的收集與分析變得尤為容易.服務方基于收集到的空間數據能夠提高企業服務質量，以及開發出更具個性化的應用軟件.近似k-近鄰(knearest neighbor,kNN)查詢是空間數據庫與空間數據挖掘中的典型應用之一.例如，圖1表示100萬條紐約出租車位置數據(NYC)的散列圖，給出kNN查詢q1，要求返回與q1之間的距離滿足r約束的6(k=6)個空間近鄰位置點.然而，在響應q1查詢的過程中，不可信的服務方有可能泄露6位乘車者或者查詢者的個人空間位置數據，進而威脅個人的自身安全.主要原因是服務方收集了個人的原始空間數據，使得個人無法掌控自己的空間隱私數據.本地化差分隱私保護技術[1]的出現使得用戶擾動自身數據之后再響應收集者的需求.目前基于本地化差分隱私著眼于頻率估計、均值估計等研究，而涉及空間近似kNN查詢的工作卻很少.

Fig. 1 Spatial kNN queries on NYC圖1 基于紐約出租車數據的空間kNN查詢

在響應圖1中的q1查詢時，每個用戶位置所對應的經緯度為個人的隱私信息.在利用本地化差分隱私對所有用戶位置數據進行保護的過程中，通常需要對其進行本地編碼與擾動.0/1編碼是用戶數據常用的編碼技術.Basic-Rappor[2]算法利用0/1編碼方案把用戶數據編碼成值域大小的二進制串.然而，該算法的誤差與通信代價直接受值域大小的影響.Rappor[2]算法結合0/1編碼與布隆過濾技術將長度為整個值域的二進制串Hash到較小的空間，減小了通信代價.不同于Rappor算法，UE[3]算法結合0/1編碼與按位擾動技術實現了二進制串的保護，同時OUE[3]算法的誤差擺脫了值域大小的影響.然而，這4種算法在保護用戶位置時存在3點不足：1)無法滿足保距性，即原始空間中近鄰的數據點經過本地擾動后不再是近鄰關系；2)會破壞用戶位置經緯度的關聯性；3)缺乏合理的數據結構來索引擾動后的空間數據點.

BV[4]算法利用連續區間分割與閾值過濾技術把數值數據嵌入匿名的漢明空間，再結合匿名空間求解數值數據之間的相似性.BV算法實現了匿名空間計算的保距性.然而，該算法存在隱私泄露風險[5]，并且不適合大值域數值數據.DPRL[5]算法結合BV編碼與Rappor擾動實現了滿足本地化差分隱私的相似性度量.盡管DPRL實現了相似性計算過程的保距性，然而該算法存在缺乏對漢明空間壓縮以及經緯度關聯性易被破壞方面的不足.結合DPRL算法的不足，LSHPM[6]算法結合局部敏感Hash(locality-sensitive hashing, LSH)[7]與按位擾動技術實現了數據相似性度量.該算法利用Hash技術壓縮了整個漢明空間，并利用單Hash表索引擾動之后的數據，實現了近似kNN查詢.然而，該算法卻存在沒有充分利用LSH數據結構索引特性，即如何利用多Hash表與多Hash函數來提高kNN搜索碰撞概率方面的不足.總而言之，目前還沒有一個行之有效且滿足本地化差分隱私的空間kNN查詢方法能夠同時克服文獻[4-6]所述算法帶來的挑戰.為此，本文基于本地化差分隱私技術提出了2種空間kNN查詢算法以解決文獻[2-6]所述算法存在的問題.

本文主要貢獻有3個方面：

1) 為了有效解決現有0/1編碼機制不能保持用戶經緯度之間的關聯性以及0/1串過長帶來的通信代價過大問題，本文首先結合歐氏空間與漢明空間之間的映射關系提出了Embed嵌入算法，該算法能夠將用戶的位置嵌入到漢明空間.結合嵌入操作所得到的0/1串，提出了基于LSH數據結構的0/1串壓縮算法，該壓縮算法充分利用多Hash表索引與多Hash函數映射2方面優點來實現空間位置的保距性.

2) 為了提高kNN查詢結果的可用性，本文利用隱私預算分割與用戶分組策略設計了2種近鄰kNN查詢算法PELSH與PULSH.基于這2類算法，設計了4類本地擾動算法PELSHB,PELSHG,PULSHB與PULSHG.收集者通過這4類擾動算法重構多Hash表結構.

3) 理論分析了本文提出的算法滿足ε-本地化差分隱私以及響應kNN查詢的誤差邊界.通過真實數據實驗分析，本文所設計的近似空間kNN查詢算法具有較高的可用性和查詢準確性.

1 相關工作

本地化差分隱私保護模型通常在假設收集者不可信的情況下收集用戶的敏感數據.每個用戶本地編碼與本地擾動自身數據，然后報告給收集者.本地化差分隱私目前的研究主要集中于頻率估計[3,8-9]與均值估計[10-11].GRR[8]機制在WRR[9]機制的基礎上以直接編碼方式轉換用戶數據，然后將用戶數據擾動成原始值域中的某個值.該機制的估計誤差容易受到原始數據值域的影響，值域過大導致誤差過高.Duchi等人[10]所提的算法通過數值離散化與本地擾動操作，估計某連續區間中的均值.然而，該算法通常造成擾動結果過大地偏離真實值.PM[11]算法能夠將某連續區間中的真實值擾動到一個連續區間，并給出相應的擾動邊界.在隱私預算比較大時，PM算法優于Duchi等人的算法.

本地化差分隱私環境下，收集者通常結合層次結構設計隱私預算分割與用戶分組策略來提高估計精度.PrivTrie[12]算法是用戶分組與隱私預算分割策略的典型代表，該算法利用這2種策略重構前綴樹，并結合前綴樹挖掘頻繁項.HH[13]算法與HI[14]算法分別利用B-ary樹對用戶數據進行索引，并利用樹層次結構實現用戶分組.PLDP[15]算法利用分類樹結構實現了用戶分組，結合分類樹與SHist[16]算法收集所有空間用戶的位置數據，并實現用戶個性化隱私保護需求.然而，該算法的擾動方法沒有顧及空間位置數據近鄰性.GT-R[17]算法利用網格編碼與四分樹索引實現了用戶分組，利用OUE[3]算法進行擾動，并能夠較高精度地響應空間范圍查詢.然而，該算法在編碼與擾動過程中沒有考慮如何保距.此外，D-Privacy[18]機制結合空間位置之間的距離約束實現了空間范圍與頻率查詢，然而該機制由于缺少空間索引而無法直接應用于近似kNN查詢.目前，支持保距編碼機制且滿足本地化差分隱私的算法包括DPRL[5]與LSHPM[6].其中，DPRL算法結合BV[4]編碼與Rappor[2]機制實現了字符串匹配，但該算法沒有考慮字符串整個值域對匹配精度的影響；LSHPM算法利用LSH結構實現近鄰查找時的保距性，然而該算法沒有充分利用LSH結構特征來提高查找的碰撞概率.因此，針對文獻[4-6]所提算法的不足，本文提出了2種基于局部敏感Hash結構的空間kNN查詢算法，這2類算法不但能夠適用于大規模空間數據，還能夠比較精確地響應kNN近似查詢.

2 定義與問題

2.1 本地化差分隱私

本地化差分隱私保護技術通常要求用戶本地編碼與擾動自己的數據，把擾動之后的數據匯報給收集者，從而使個人隱私不被泄露.本地化差分隱私的形式化定義如下所示.

定義1.ε-本地化差分隱私.給定一個隨機算法M及其定義域Dom(M)和輸出值域Range(M)，若M在任意2條不同空間點pi與pj(pi,pj∈Dom(M))上得到相同輸出結果O(O∈Range(M))的概率滿足不等式：

Pr[M(pi)∈O]≤eε×Pr[M(pj)∈O],

(1)

則M滿足ε-本地化差分隱私.其中,ε為隱私預算.

本地化差分隱私通常具有序列組合性質.

2.2 隨機應答機制

隨機應答機制[9]是實現本地化差分隱私的常用技術之一.該機制主要關注用戶在響應敏感布爾問題時，通常以概率p真實應答，以1-p的概率給出相反的應答.收集者利用噪音結果對真實的統計結果進行估計分析.目前，基于隨機應答機制出現了以GRR與按位擾動(BitP)為代表的本地擾動算法.

1) GRR[8]算法.給定空間點pi與pj，且pi,pj∈{1,2,…,d}，其中d為值域大小，GRR算法為：

(2)

其中,e表示自然對數的底數，ε為隱私預算.

2) BitP[2]算法.給定空間點pi，利用0/1編碼將其轉換成二進制向量B.對于B中任意一個比特位Bi，BitP算法擾動為：

(3)

2.3 空間近似kNN查詢

高效的索引結構是響應空間kNN查詢的關鍵技術之一.以KD-樹為代表的層次結構可以有效響應kNN查詢.然而，在本地化差分隱私環境下構建KD-樹比較困難與低效，其主要原因是構建該結構具有數據相關性，與具體的數據分布緊密關聯.不同于KD-樹，局部敏感Hash結構通過設計特殊的Hash簇，使得2個近鄰空間數據點以較高的概率映射成相同的Hash值，而使2個距離比較遠的空間數據點以較低的概率映射成相同的Hash值.該結構具有較強的保距性，其形式化定義為：

定義2.LSH[7].給定空間查詢距離約束參數r與近似比率參數c，若Hash簇H對于空間中任意2個點pi與pj滿足：

1) 若dis(pi,pj)≤r，則Pr[h(pi)=h(pj)]≥P1；

2) 若dis(pi,pj)≥cr，則Pr[h(pi)=h(pj)]≤P2.

則H被稱為(r，cr，P1，P2)-敏感的，其中dis(pi,pj)表示pi與pj之間的距離，Pr[h(pi)=h(pj)]表示pi與pjHash值相等的碰撞概率，常量c>1，P1>P2.

因此，本文要解決的問題是在設計滿足本地化差分隱私的空間kNN查詢算法的同時，要盡可能獲得精度較高的查詢結果.

3 基于本地化差分隱私的近似kNN查詢算法

在設計滿足本地化差分隱私的空間近似kNN查詢算法時需要考慮2條原則：1)所設計的本地編碼與擾動算法盡可能滿足保距性；2)所設計的kNN查詢算法盡可能返回較高精度的查詢結果.針對這2條原則，本文利用位置空間到漢明空間嵌入技術與本地敏感Hash技術對空間數據進行編碼與Hash壓縮，結合壓縮編碼設計相應的擾動算法.

3.1 漢明空間嵌入與LSH Hash壓縮

由于漢明空間中容易找到合適的LSH Hash簇，每個用戶對自己的位置pi(pi∈D)進行漢明空間轉換.結合文獻[7]，本文提出了一種空間位置0/1編碼算法，具體細節如算法1所示：

算法1.Embed.

輸入：第i個用戶的位置pi且pi∈D、D中所有經度與維度的最大值M;

輸出：pi的漢明編碼bi.

⑤ returnbi.

Embed算法的主要目的是對每個用戶的空間位置進行0/1編碼，進而形成二進串.例如M=3，pi=(1,2)，則unary(bi1)=(100)，unary(bi2)=(110)，進而可知b的長度為6且bi=(100110).如果每個用戶直接對長度為2M的0/1串擾動并報告給收集者，會破壞經緯度之間的關聯性以及造成較高的通信代價.為此，本文利用具有保距性的LSH Hash簇對每個用戶的0/1串進行壓縮.LSH Hash壓縮與kNN查詢原理如圖2所示：

Fig. 2 Theory and example of LSH圖2 LSH原理與例子

由定義2可知，滿足條件1與條件2即可獲得LSH Hash簇H.若漢明距離dis(pi,pj)≤r，則表示pi與pj近鄰；dis(pi,pj)≥cr，則表示pi與pj不近鄰.例如p1=(1,2),p3=(2,3).p1與p3的0/1編碼分別為(100110),(110111).結合H與Hash表g1，如圖2(b)所示，隨機選擇2個Hash函數h3與h4.利用h3和h4壓縮p1與p3的編碼，即可獲得g1(100110)=01，g1(110111)=01.因此，p1與p3被Hash到g1的01編碼所對應的桶內.

獲得Hash簇H后，如何計算條件1與條件2中的P1與P2至關重要.根據Embed算法，碰撞概率P1與P2可以表示為

(4)

(5)

根據式(4)(5)可知，當參數r,M與c確定后，即可獲得P1,P2.例如p1=(1,2),p3=(2,3),M=3,c=2，漢明距離r=dis(p1,p3)=2，則P1=2/3，P2=1/3.然而，合適的LSH Hash函數應該使P1盡量大且P2盡量小.結合文獻[7]發現，通過增加Hash表個數l以及增加每個Hash表的Hash函數個數m，可以增大P1與P2之間的間隔，進而提高2個近鄰點被Hash到同一個桶的碰撞概率.具體技術細節為：

結合圖2(a)，假設有l個Hash表，每個Hash表對應1個Hash簇H.從每個Hash簇H中隨機抽取m個Hash函數，形成該Hash表的串型Hash函數，即gi={h1,h2,…,hm},1≤i≤l.則l個Hash表所對應的串型Hash函數表示為G={g1,g2,…,gl}.給定任意1個空間位置pi以及任意1個空間查詢點q，利用擁有l個Hash表的Hash函數G表示pi與q之間的碰撞概率：

Pr[G(pi)=G(q)]= 1-[1-Pr[g1(pi)=g1(q)]]×…× [1-Pr[gl(pi)=gl(q)]]= 1-[1-(P1)m]l,

(6)

其中,Pr[gi(pi)=gi(q)]=(P1)m.

根據1-[1-(P1)m]l>(P1)m可知，多Hash表的碰撞概率明顯高于單Hash表.

例如p1=(1,1),p2=(2,1),p3=(1,2),p4=(2,2),p5=(3,2).相應的0/1編碼分別為(100100),(110100),(100110),(110110),(111110).設m=2,l=3，則G={g1,g2,g3},gi={h1,h2}.設g1,g2,g3分別抽取上述p1～p5的0/1編碼的第2與第4個位置、第1與第2個位置、第3與第5個位置.則p1～p5這5個點分別在g1,g2,g3中的位置如圖2(b)所示.給定查詢點q=(3,3)，相應的0/1編碼為(111111).遍歷g1,g2,g3可得p5是q的最近鄰.

3.2 基于LSH的空間kNN查詢算法

由文獻[6]可知，當攻擊者獲得Hash函數{h1,h2,…,hm}后，可獲取目標用戶的隱私位置信息.因此，本文保護l個Hash表的構建過程，并遍歷所有Hash表響應kNN查詢.給定隱私預算ε，如何構建l個Hash表是個大挑戰.本文分別利用隱私預算分割與用戶分組策略設計了2種近似kNN查詢算法.

3.2.1 基于隱私預算分割的kNN查詢算法

本節首先基于多Hash表與多Hash函數的LSH結構提出PELSH算法，該算法包括本地漢明空間嵌入、用戶位置本地擾動、收集者重構多Hash表結構以及響應kNN查詢等操作.該算法具體細節為：

算法2.PELSH算法.

輸入：n個用戶的空間位置、查詢點q、查詢半徑r、Hash表個數l、Hash函數個數m、隱私預算ε、經緯度最大值M；

輸出：滿足本地差分隱私的kNN集合S.

①S←?;

② 收集者初始化l個Hash表{g1,g2,…,gl}，每個gi包含m個Hash函數;

③ 收集者發送l個Hash表和m個Hash函數給每一個用戶;

用戶端：

④ for對每個Hash表gido

⑤ for每個用戶i=1 tondo

⑥ 用戶i把自身位置pi漢明嵌入為bi,bi←Embed(pi,M);

⑦ 用戶i利用LSH對bi進行Hash壓縮

⑩ end for

收集者端：

PELSH算法利用隱私預算分割策略解決近似kNN查詢問題.首先收集者創建l個空Hash表并共享給n個用戶(步驟②③).每個用戶利用Embed,LSH將自身數據轉換與壓縮成0/1串，利用LRR機制本地擾動壓縮后的0/1串，并將擾動值報告給收集者(步驟④～).收集者結合所有用戶的報告值重構每個Hash表，并利用重構之后的l個Hash表響應kNN查詢(步驟～).

根據PELSH算法的步驟⑧可知，每個用戶利用LRR算對壓縮結果進行本地擾動.擾動后的0/1串直接決定著某用戶位置的Hash桶地址.基于此，本文分別結合BitP機制與GRR機制設計2種本地擾動算法PELSHB與PELSHG，并利用PELSHB與PELSHG替換步驟⑧中LRR來擾動LSH壓縮后的0/1串.2種算法的細節為：

(7)

(8)

其中,b*表示值域2m中的任意值.

定理1.PELSHB算法與PELSHG算法滿足ε-本地化差分隱私.

證畢.

盡管收集者采用PELSHB算法與PELSHG算法收集了n個用戶的位置并重構了l個Hash表，但對于任意1個Hash表，我們期望它所對應的任意1個Hash桶中空間位置點計數滿足無偏性.

證畢.

證畢.

定理4.利用PELSHB算法構建l個Hash表，

至少以概率1-β成立.

根據伯恩斯坦不等式可知：

證畢.

定理5.利用PELSHG算法構建l個Hash表，

根據伯恩斯坦不等式可知：

證畢.

由算法2可知，通過增加Hash表個數l和Hash函數個數m可以提升kNN查找的碰撞概率，如式(6)所示.然而，PELSH算法卻是在分割隱私預算的前提下構建l個Hash表索引結構.若l值過大，則PELSHB算法與PELSHG算法會產生過大的誤差.因此，本文結合用戶分組策略來實現kNN查詢.

3.2.2 基于用戶分組的kNN查詢算法

本節主要闡述PULSH算法的具體實現細節.

算法3.PULSH算法.

輸入：n個用戶的位置數據、查詢點q、查詢半徑r、Hash表個數l、Hash函數個數m、隱私預算ε、經緯度最大值M；

輸出：滿足本地差分隱私的kNN集合S.

① 與算法2的步驟①～③相同;

② 把n個用戶隨機分成l組，分別記為C1,C2,

用戶端：

③ for每個Hash表gi(1≤i≤l) do

④ for對Cj中的每個用戶do

⑤ 與算法2的步驟⑥⑦相同;

⑧ end for

⑨ end for

收集者端：

⑩ for每個Hash表gido

PULSH算法核心思路是利用用戶分組策略重構l個Hash表.首先是對n個用戶進行隨機均勻分組(步驟②).每個用戶利用LRR機制擾動LSH壓縮后的0/1串，并將擾動值發送給收集者(步驟⑥⑦).收集者結合所有用戶的報告值重構每個Hash表，并響應kNN查詢(步驟⑩～).

根據PULSH算法的步驟⑥可知，如何利用LRR擾動0/1串是該算法的關鍵.類似于PELSH算法，本文同樣結合BitP機制與GRR機制設計2種擾動算法PULSHB與PULSHG，并用這2種算法替換步驟⑥中的LRR.

(9)

(10)

其中,b*表示值域2m中的任意值.

定理6.PULSHB算法與PULSHG算法滿足ε-本地化差分隱私.

證畢.

收集者利用PULSHB與PULSHG算法重構l個Hash表，并結合重構的Hash表響應kNN查詢.類似于PELSHB與PELSHG算法，對于任意1個Hash表，它的任意1個Hash桶中位置點計數應滿足無偏性.

定理7.n個用戶的位置點經過PULSHB算法處理后，分布在l個Hash表中.對應任意1個Hash

證畢.

證畢.

至少以概率1-β成立.

根據伯恩斯坦不等式可知：

證畢.

至少以概率1-β成立.

根據伯恩斯坦不等式可知：

證畢.

3.2.3 4種本地擾動算法的優劣分析

定理1～10分別估計了每個桶計數的無偏性與最大偏差.下面分析PELSHB,PELSHG,PULSHB,PULSHG彼此的優劣.設Error(PELSHB),Error(PELSHG),Error(PULSHB),Error(PULSHG)為各自的最大偏差.隱私預算分割策略下的算法為PELSHB與PELSHG；用戶分組策略的算法為PULSHB與PULSHG.

1) 基于隱私預算分割與用戶分組的算法對比.

(11)

(12)

2) PULSHB和PULSHG、PELSHB和PELSHG對比.

根據式(13)(14)可知，當Hash表中Hash函數的個數m<10時，Error(PULSHB)>Error(PULSHG)，Error(PELSHB)>Error(PELSHG).然而，當Hash函數個數m≥10時，Error(PULSHB)

(13)

(14)

4 實驗結果與分析

實驗平臺是4核Intel CPU(4 GHz)，8 GB內存，Win7系統，代碼采用Python實現.實驗采用4個數據集，分別為Landmark數據集、Checkin數據集、NYC數據集以及Beijing數據集.其中Landmark數據集從infochimps平臺獲得，記錄了2010年人口普查時用戶到過的美國48個州的地標位置，總共包含870 051條數據；Checkin數據集從基于地理位置的社交網站Gowalla獲取，記錄了在2009-02—2010-10期間用戶簽到的時間和位置信息，包含100萬條記錄；NYC數據集是2011年整個12個月內紐約市出租車的乘車和下車的地理坐標數據，包含1 000萬條信息；Beijing數據集是2011年2月某一周內北京市10 357輛出租車的乘車和下車地理坐標數據，包含1 500萬條信息.4種數據集具體細節與可視化結果分別如表1與圖3所示：

Table 1 Characteristics of Datasets表1 數據集的屬性

結合4個數據集，采用相對誤差(relative error,RE)、召回率(Recall)、精度(Precision)，度量HammingP,DPRL,LSHPM,PELSHB,PELSHG,PULSHB,PULSHG這7種算法的查詢精度，其中HammingP是把位置數據嵌入到漢明空間后直接進行比特擾動的算法.隱私參數ε的選取分別為0.1,0.3,0.5,0.7,0.9,1.1.為了便于實驗圖的展示，我們對RE,Recall,Precision的實驗結果取對數，并且加上最大偏移量.在4.1節中，本文提出的4種算法參數設置為l=5，m=9；4.2節和4.3節中，l=5.

Fig. 3 Visualization of four datasets圖3 4個數據集的可視化結果

Fig. 4 Comparisons on Landmark圖4 基于Landmark數據集的算法對比

Fig. 5 Comparisons on Checkin圖5 基于Checkin數據集的算法對比

Fig. 6 Comparisons on NYC圖6 基于NYC數據集的算法對比

4.1 基于ε變化的7種算法性能比較

結合4種數據集，固定參數l與m，改變ε，對7種算法進行性能對比分析.圖4(a)～圖4(c)、圖5(a)～圖5(c)、圖6(a)～圖6(c)和圖7(a)～圖7(c)描述了HammingP,DPRL,LSHPM,PELSHB,PELSHG,PULSHB,PULSHG算法的RE,Recall,Precision的比較結果.當k=50時，隨著ε的增加，所有算法的RE值均呈下降趨勢，Recall和Precision呈上升趨勢，原因是噪音的多少與ε成反比，ε越大，RE越小，Recall和Precision越高.例如，在Landmark數據集上，PELSHB,PELSHG,PULSHB,PULSHG算法均優于其他3種算法.在ε=1.1時，HammingP和DPRL算法的RE是PULSHG算法的近10倍；LSHPM算法的RE是PULSHG算法的近4倍；PULSHG的Recall是HammingP,DPRL,LSHPM算法的近20倍，Precision是這3種算法的近3倍.此外，相比HammingP和DPRL算法，本文采用LSH對數據進行壓縮轉換，使其在具有保距性的前提下，減小隱私預算分割的次數，增加Recall與Precision；相比LSHPM算法，本文提出的4種擾動算法增加了相似數據的碰撞概率，提高了查詢精度.

4.2 基于k變化的7種算法性能比較

圖4(d)、圖5(d)、圖6(d)和圖7(d)描述了HammingP,DPRL,LSHPM,PELSHB,PELSHG,PULSHB,PULSHG算法隨著近鄰個數k的增加導致RE值的變化情況.由實驗結果可以發現，當ε=1.1時，隨著近鄰個數k從10增加到110，RE呈現先減少后增加的趨勢，其原因是查詢的近鄰位置越多，查詢的范圍越大，包含的查詢單個點數越多，累計誤差越大，導致精度隨著查詢范圍的增大而降低.當k=50時，在4個數據集上，PULSHG算法最優.在Checkin數據集上，PULSHG算法RE值是HammingP和DPRL算法的近90倍，是LSHPM的15倍，用戶分組相比于隱私預算分割方法精度提高近5倍.

4.3 基于m變化的7種算法性能比較

圖4(e)(f)、圖5(e)(f)、圖6(e)(f)和圖7(e)(f)描述了算法PELSHB,PELSHG,PULSHB,PULSHG的RE,Recall,Precision的比較結果.由圖(e)可以發現，隨著Hash函數的個數m的增加，RE值先降低后增加，其中m<10時PELSHG優于PELSHB，m≥10時PELSHG的誤差大于PELSHB.用戶分組算法的臨界點為m=12.在m<12時，PULSHG優于PULSHB；在m≥12時，PULSHG的誤差大于PULSHB.按照Hash地址擾動方法的誤差隨著Hash函數個數的增加呈指數形式增加.m=12與3.2.3節的理論分析存在一定出入，其原因是PULSHB與PULSHG最大偏差理論分析與參數l無關，而具體實驗過程與l相關.從圖4(f)、圖5(f)、圖6(f)和圖7(f)中可以發現，PELSHB,PELSHG,PULSHB,PULSHG算法的Recall(R-PELSHB,R-PELSHG,R-PULSHB,R-PULSHG)與Precision(P-PELSHB,P-PELSHG,P-PULSHB,P-PULSHG)為負相關關系，Recall均下降，Precision均上升.從整體來看，用戶分組的算法優于隱私預算分割，其原因是用戶分組情況下每個用戶的ε是隱私預算分割情況下的l倍，ε越小誤差越大，其對應的Recall與Precision越低.

5 結束語

本文針對本地化差分隱私保護下空間kNN近似查詢存在的問題，結合現有0/1編碼機制與擾動機制存在的不足，提出了基于LSH結構的kNN近似查詢算法.該類算法通過漢明空間嵌入、LSH Hash壓縮、隱私預算分割與用戶分組等策略實現了空間數據高精度收集.從本地化差分隱私定義角度分析文中所提出的算法滿足ε-本地化差分隱私.最后通過4種真實的空間數據集驗證了本文算法的kNN近似查詢精度.實驗結果表明，本文算法明顯優于現有的同類方法.未來工作考慮如何結合本地化差分隱私與LSH實現高維數據空間中的kNN查詢問題.

作者貢獻聲明：張嘯劍負責論文的算法設計、相關定理設置及論證，并負責整篇論文的撰寫；徐雅鑫負責論文算法的實現與實驗結果分析；孟小峰指導論文撰寫的邏輯性與算法的合理性.