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

張嘯劍 徐雅鑫 孟小峰

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

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

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

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

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

本文主要貢獻(xiàn)有3個(gè)方面：

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

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

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

1 相關(guān)工作

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

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

2 定義與問題

2.1 本地化差分隱私

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

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

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

(1)

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

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

2.2 隨機(jī)應(yīng)答機(jī)制

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

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

(2)

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

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

(3)

2.3 空間近似kNN查詢

高效的索引結(jié)構(gòu)是響應(yīng)空間kNN查詢的關(guān)鍵技術(shù)之一.以KD-樹為代表的層次結(jié)構(gòu)可以有效響應(yīng)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è)計(jì)特殊的Hash簇，使得2個(gè)近鄰空間數(shù)據(jù)點(diǎn)以較高的概率映射成相同的Hash值，而使2個(gè)距離比較遠(yuǎn)的空間數(shù)據(jù)點(diǎn)以較低的概率映射成相同的Hash值.該結(jié)構(gòu)具有較強(qiáng)的保距性，其形式化定義為：

定義2.LSH[7].給定空間查詢距離約束參數(shù)r與近似比率參數(shù)c，若Hash簇H對于空間中任意2個(gè)點(diǎn)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è)計(jì)滿足本地化差分隱私的空間kNN查詢算法的同時(shí)，要盡可能獲得精度較高的查詢結(jié)果.

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

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

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

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

算法1.Embed.

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

輸出：pi的漢明編碼bi.

⑤ returnbi.

Embed算法的主要目的是對每個(gè)用戶的空間位置進(jìn)行0/1編碼，進(jìn)而形成二進(jìn)串.例如M=3，pi=(1,2)，則unary(bi1)=(100)，unary(bi2)=(110)，進(jìn)而可知b的長度為6且bi=(100110).如果每個(gè)用戶直接對長度為2M的0/1串?dāng)_動(dòng)并報(bào)告給收集者，會(huì)破壞經(jīng)緯度之間的關(guān)聯(lián)性以及造成較高的通信代價(jià).為此，本文利用具有保距性的LSH Hash簇對每個(gè)用戶的0/1串進(jìn)行壓縮.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)所示，隨機(jī)選擇2個(gè)Hash函數(shù)h3與h4.利用h3和h4壓縮p1與p3的編碼，即可獲得g1(100110)=01，g1(110111)=01.因此，p1與p3被Hash到g1的01編碼所對應(yīng)的桶內(nèi).

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

(4)

(5)

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

結(jié)合圖2(a)，假設(shè)有l(wèi)個(gè)Hash表，每個(gè)Hash表對應(yīng)1個(gè)Hash簇H.從每個(gè)Hash簇H中隨機(jī)抽取m個(gè)Hash函數(shù)，形成該Hash表的串型Hash函數(shù)，即gi={h1,h2,…,hm},1≤i≤l.則l個(gè)Hash表所對應(yīng)的串型Hash函數(shù)表示為G={g1,g2,…,gl}.給定任意1個(gè)空間位置pi以及任意1個(gè)空間查詢點(diǎn)q，利用擁有l(wèi)個(gè)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).相應(yīng)的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個(gè)位置、第1與第2個(gè)位置、第3與第5個(gè)位置.則p1～p5這5個(gè)點(diǎn)分別在g1,g2,g3中的位置如圖2(b)所示.給定查詢點(diǎn)q=(3,3)，相應(yīng)的0/1編碼為(111111).遍歷g1,g2,g3可得p5是q的最近鄰.

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

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

3.2.1 基于隱私預(yù)算分割的kNN查詢算法

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

算法2.PELSH算法.

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

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

①S←?;

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

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

用戶端：

④ for對每個(gè)Hash表gido

⑤ for每個(gè)用戶i=1 tondo

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

⑦ 用戶i利用LSH對bi進(jìn)行Hash壓縮

⑩ end for

收集者端：

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

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

(7)

(8)

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

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

證畢.

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

證畢.

證畢.

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

至少以概率1-β成立.

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

證畢.

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

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

證畢.

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

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

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

算法3.PULSH算法.

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

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

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

② 把n個(gè)用戶隨機(jī)分成l組，分別記為C1,C2,

用戶端：

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

④ for對Cj中的每個(gè)用戶do

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

⑧ end for

⑨ end for

收集者端：

⑩ for每個(gè)Hash表gido

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

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

(9)

(10)

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

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

證畢.

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

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

證畢.

證畢.

至少以概率1-β成立.

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

證畢.

至少以概率1-β成立.

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

證畢.

3.2.3 4種本地?cái)_動(dòng)算法的優(yōu)劣分析

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

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

(11)

(12)

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

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

(13)

(14)

4 實(shí)驗(yàn)結(jié)果與分析

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

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

結(jié)合4個(gè)數(shù)據(jù)集，采用相對誤差(relative error,RE)、召回率(Recall)、精度(Precision)，度量HammingP,DPRL,LSHPM,PELSHB,PELSHG,PULSHB,PULSHG這7種算法的查詢精度，其中HammingP是把位置數(shù)據(jù)嵌入到漢明空間后直接進(jìn)行比特?cái)_動(dòng)的算法.隱私參數(shù)ε的選取分別為0.1,0.3,0.5,0.7,0.9,1.1.為了便于實(shí)驗(yàn)圖的展示，我們對RE,Recall,Precision的實(shí)驗(yàn)結(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個(gè)數(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，改變?chǔ)牛瑢?種算法進(jìn)行性能對比分析.圖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é)果.當(dāng)k=50時(shí)，隨著ε的增加，所有算法的RE值均呈下降趨勢，Recall和Precision呈上升趨勢，原因是噪音的多少與ε成反比，ε越大，RE越小，Recall和Precision越高.例如，在Landmark數(shù)據(jù)集上，PELSHB,PELSHG,PULSHB,PULSHG算法均優(yōu)于其他3種算法.在ε=1.1時(shí)，HammingP和DPRL算法的RE是PULSHG算法的近10倍；LSHPM算法的RE是PULSHG算法的近4倍；PULSHG的Recall是HammingP,DPRL,LSHPM算法的近20倍，Precision是這3種算法的近3倍.此外，相比HammingP和DPRL算法，本文采用LSH對數(shù)據(jù)進(jìn)行壓縮轉(zhuǎn)換，使其在具有保距性的前提下，減小隱私預(yù)算分割的次數(shù)，增加Recall與Precision；相比LSHPM算法，本文提出的4種擾動(dòng)算法增加了相似數(shù)據(jù)的碰撞概率，提高了查詢精度.

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

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

5 結(jié)束語

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

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