張嘯劍 徐雅鑫 孟小峰

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

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

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

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

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

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

1) 為了有效解決現(xiàn)有0/1編碼機制不能保持用戶經(jīng)緯度之間的關(guān)聯(lián)性以及0/1串過長帶來的通信代價過大問題，本文首先結(jié)合歐氏空間與漢明空間之間的映射關(guān)系提出了Embed嵌入算法，該算法能夠?qū)⒂脩舻奈恢们度氲綕h明空間.結(jié)合嵌入操作所得到的0/1串，提出了基于LSH數(shù)據(jù)結(jié)構(gòu)的0/1串壓縮算法，該壓縮算法充分利用多Hash表索引與多Hash函數(shù)映射2方面優(yōu)點來實現(xiàn)空間位置的保距性.

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

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

1 相關(guān)工作

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

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

2 定義與問題

2.1 本地化差分隱私

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

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

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

(1)

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

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

2.2 隨機應答機制

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

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

(2)

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

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

(3)

2.3 空間近似kNN查詢

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

定義2.LSH[7].給定空間查詢距離約束參數(shù)r與近似比率參數(shù)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.

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

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

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

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

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

算法1.Embed.

輸入：第i個用戶的位置pi且pi∈D、D中所有經(jīng)度與維度的最大值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串擾動并報告給收集者，會破壞經(jīng)緯度之間的關(guān)聯(lián)性以及造成較高的通信代價.為此，本文利用具有保距性的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).結(jié)合H與Hash表g1，如圖2(b)所示，隨機選擇2個Hash函數(shù)h3與h4.利用h3和h4壓縮p1與p3的編碼，即可獲得g1(100110)=01，g1(110111)=01.因此，p1與p3被Hash到g1的01編碼所對應的桶內(nèi).

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

(4)

(5)

根據(jù)式(4)(5)可知，當參數(shù)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函數(shù)應該使P1盡量大且P2盡量小.結(jié)合文獻[7]發(fā)現(xiàn)，通過增加Hash表個數(shù)l以及增加每個Hash表的Hash函數(shù)個數(shù)m，可以增大P1與P2之間的間隔，進而提高2個近鄰點被Hash到同一個桶的碰撞概率.具體技術(shù)細節(jié)為：

結(jié)合圖2(a)，假設(shè)有l(wèi)個Hash表，每個Hash表對應1個Hash簇H.從每個Hash簇H中隨機抽取m個Hash函數(shù)，形成該Hash表的串型Hash函數(shù)，即gi={h1,h2,…,hm},1≤i≤l.則l個Hash表所對應的串型Hash函數(shù)表示為G={g1,g2,…,gl}.給定任意1個空間位置pi以及任意1個空間查詢點q，利用擁有l(wèi)個Hash表的Hash函數(shù)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.

根據(jù)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).設(shè)m=2,l=3，則G={g1,g2,g3},gi={h1,h2}.設(shè)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函數(shù){h1,h2,…,hm}后，可獲取目標用戶的隱私位置信息.因此，本文保護l個Hash表的構(gòu)建過程，并遍歷所有Hash表響應kNN查詢.給定隱私預算ε，如何構(gòu)建l個Hash表是個大挑戰(zhàn).本文分別利用隱私預算分割與用戶分組策略設(shè)計了2種近似kNN查詢算法.

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

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

算法2.PELSH算法.

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

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

①S←?;

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

③ 收集者發(fā)送l個Hash表和m個Hash函數(shù)給每一個用戶;

用戶端：

④ for對每個Hash表gido

⑤ for每個用戶i=1 tondo

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

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

⑩ end for

收集者端：

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

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

(7)

(8)

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

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

證畢.

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

證畢.

證畢.

定理4.利用PELSHB算法構(gòu)建l個Hash表，

至少以概率1-β成立.

根據(jù)伯恩斯坦不等式可知：

證畢.

定理5.利用PELSHG算法構(gòu)建l個Hash表，

根據(jù)伯恩斯坦不等式可知：

證畢.

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

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

本節(jié)主要闡述PULSH算法的具體實現(xiàn)細節(jié).

算法3.PULSH算法.

輸入：n個用戶的位置數(shù)據(jù)、查詢點q、查詢半徑r、Hash表個數(shù)l、Hash函數(shù)個數(shù)m、隱私預算ε、經(jīng)緯度最大值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算法核心思路是利用用戶分組策略重構(gòu)l個Hash表.首先是對n個用戶進行隨機均勻分組(步驟②).每個用戶利用LRR機制擾動LSH壓縮后的0/1串，并將擾動值發(fā)送給收集者(步驟⑥⑦).收集者結(jié)合所有用戶的報告值重構(gòu)每個Hash表，并響應kNN查詢(步驟⑩～).

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

(9)

(10)

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

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

證畢.

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

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

證畢.

證畢.

至少以概率1-β成立.

根據(jù)伯恩斯坦不等式可知：

證畢.

至少以概率1-β成立.

根據(jù)伯恩斯坦不等式可知：

證畢.

3.2.3 4種本地擾動算法的優(yōu)劣分析

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

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

(11)

(12)

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

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

(13)

(14)

4 實驗結(jié)果與分析

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

Table 1 Characteristics of Datasets表1 數(shù)據(jù)集的屬性

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

Fig. 3 Visualization of four datasets圖3 4個數(shù)據(jù)集的可視化結(jié)果

Fig. 4 Comparisons on Landmark圖4 基于Landmark數(shù)據(jù)集的算法對比

Fig. 5 Comparisons on Checkin圖5 基于Checkin數(shù)據(jù)集的算法對比

Fig. 6 Comparisons on NYC圖6 基于NYC數(shù)據(jù)集的算法對比

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

結(jié)合4種數(shù)據(jù)集，固定參數(shù)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的比較結(jié)果.當k=50時，隨著ε的增加，所有算法的RE值均呈下降趨勢，Recall和Precision呈上升趨勢，原因是噪音的多少與ε成反比，ε越大，RE越小，Recall和Precision越高.例如，在Landmark數(shù)據(jù)集上，PELSHB,PELSHG,PULSHB,PULSHG算法均優(yōu)于其他3種算法.在ε=1.1時，HammingP和DPRL算法的RE是PULSHG算法的近10倍；LSHPM算法的RE是PULSHG算法的近4倍；PULSHG的Recall是HammingP,DPRL,LSHPM算法的近20倍，Precision是這3種算法的近3倍.此外，相比HammingP和DPRL算法，本文采用LSH對數(shù)據(jù)進行壓縮轉(zhuǎn)換，使其在具有保距性的前提下，減小隱私預算分割的次數(shù)，增加Recall與Precision；相比LSHPM算法，本文提出的4種擾動算法增加了相似數(shù)據(jù)的碰撞概率，提高了查詢精度.

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

圖4(d)、圖5(d)、圖6(d)和圖7(d)描述了HammingP,DPRL,LSHPM,PELSHB,PELSHG,PULSHB,PULSHG算法隨著近鄰個數(shù)k的增加導致RE值的變化情況.由實驗結(jié)果可以發(fā)現(xiàn)，當ε=1.1時，隨著近鄰個數(shù)k從10增加到110，RE呈現(xiàn)先減少后增加的趨勢，其原因是查詢的近鄰位置越多，查詢的范圍越大，包含的查詢單個點數(shù)越多，累計誤差越大，導致精度隨著查詢范圍的增大而降低.當k=50時，在4個數(shù)據(jù)集上，PULSHG算法最優(yōu).在Checkin數(shù)據(jù)集上，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的比較結(jié)果.由圖(e)可以發(fā)現(xiàn)，隨著Hash函數(shù)的個數(shù)m的增加，RE值先降低后增加，其中m<10時PELSHG優(yōu)于PELSHB，m≥10時PELSHG的誤差大于PELSHB.用戶分組算法的臨界點為m=12.在m<12時，PULSHG優(yōu)于PULSHB；在m≥12時，PULSHG的誤差大于PULSHB.按照Hash地址擾動方法的誤差隨著Hash函數(shù)個數(shù)的增加呈指數(shù)形式增加.m=12與3.2.3節(jié)的理論分析存在一定出入，其原因是PULSHB與PULSHG最大偏差理論分析與參數(shù)l無關(guān)，而具體實驗過程與l相關(guān).從圖4(f)、圖5(f)、圖6(f)和圖7(f)中可以發(fā)現(xiàn)，PELSHB,PELSHG,PULSHB,PULSHG算法的Recall(R-PELSHB,R-PELSHG,R-PULSHB,R-PULSHG)與Precision(P-PELSHB,P-PELSHG,P-PULSHB,P-PULSHG)為負相關(guān)關(guān)系，Recall均下降，Precision均上升.從整體來看，用戶分組的算法優(yōu)于隱私預算分割，其原因是用戶分組情況下每個用戶的ε是隱私預算分割情況下的l倍，ε越小誤差越大，其對應的Recall與Precision越低.

5 結(jié)束語

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

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