基于本地差分隱私的空間范圍查詢(xún)方法

張嘯劍 付 楠 孟小峰

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

信息時(shí)代的飛速發(fā)展，用戶(hù)空間數(shù)據(jù)(例如移動(dòng)用戶(hù)位置、GPS位置、家庭住址等)的收集與分析能夠改善IT企業(yè)的軟件與服務(wù)質(zhì)量，以及向用戶(hù)提供更好的個(gè)性化體驗(yàn).然而，不可信第三方對(duì)空間數(shù)據(jù)進(jìn)行收集與分析時(shí)，個(gè)人的敏感信息有可能被泄露.例如不可信銷(xiāo)售網(wǎng)站通過(guò)收集客戶(hù)的位置信息，可以學(xué)習(xí)出客戶(hù)的購(gòu)物行為模式以及家庭住址.因此，在此情景下，用戶(hù)通常無(wú)法掌控自己的空間隱私數(shù)據(jù).本地差分隱私保護(hù)技術(shù)[1]的出現(xiàn)使得用戶(hù)可以自己擾動(dòng)自身數(shù)據(jù)之后再響應(yīng)收集者的需求.目前基于本地差分隱私著眼于頻率估計(jì)、均值估計(jì)等研究，而涉及空間范圍查詢(xún)的工作卻很少.基于空間數(shù)據(jù)的范圍查詢(xún)是空間數(shù)據(jù)分析常用的技術(shù)之一.例如圖1表示100萬(wàn)條紐約出租車(chē)位置數(shù)據(jù)(New York City data, NYC)散點(diǎn)圖，查詢(xún)框Q1要求返回曼哈頓醫(yī)院附近范圍內(nèi)的乘客數(shù)量.該查詢(xún)對(duì)應(yīng)的SQL語(yǔ)句可以表示為Q1:Select Count(*) from NYC where -14≤lat≤23 and -10≤lon≤20.

Fig. 1 Spatial range queries on NYC圖1 基于NYC的空間范圍查詢(xún)

在Q1查詢(xún)中，用戶(hù)位置所對(duì)應(yīng)的經(jīng)緯度為敏感信息.因此，用戶(hù)在共享自身位置之前，需要本地化差分隱私保護(hù)處理.而在此過(guò)程中存在諸多挑戰(zhàn)：1)收集者如何構(gòu)建高效的空間索引結(jié)構(gòu)收集用戶(hù)的報(bào)告數(shù)據(jù)；2)由于空間數(shù)據(jù)的值域通常很大，用戶(hù)采用什么樣的編碼機(jī)制與擾動(dòng)機(jī)制處理自身的空間數(shù)據(jù)；3)如何設(shè)計(jì)高效的后置處理技術(shù)來(lái)提供空間范圍查詢(xún)精度.總而言之，目前還沒(méi)有一個(gè)行之有效且滿(mǎn)足本地差分隱私的空間范圍查詢(xún)方法能夠同時(shí)克服上述3種挑戰(zhàn).為此，本文基于本地差分隱私技術(shù)提出了一種空間范圍查詢(xún)方法能夠兼顧上述的查詢(xún)需求.

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

1) 為了解決挑戰(zhàn)1，本文首先結(jié)合網(wǎng)格與四分樹(shù)結(jié)構(gòu)提出了GT-R方法.在該方法中，收集者首先利用網(wǎng)格結(jié)構(gòu)均分空間數(shù)據(jù)值域，并形成大小均等的空單元格區(qū)域；然后基于所有空單元格區(qū)域構(gòu)建四分樹(shù)索引結(jié)構(gòu)，并共享給每個(gè)用戶(hù).

2) 為了有效解決挑戰(zhàn)2，在GT-R方法中，每個(gè)用戶(hù)結(jié)合收集者發(fā)來(lái)的四分樹(shù)副本對(duì)自身位置數(shù)據(jù)進(jìn)行編碼，利用優(yōu)化隨機(jī)應(yīng)答機(jī)制與隨機(jī)采樣技術(shù)本地?cái)_動(dòng)自身位置，并把所抽樣的結(jié)點(diǎn)層次以及擾動(dòng)值匯報(bào)給收集者.

3) 為了有效解決挑戰(zhàn)3，GT-R方法結(jié)合四分樹(shù)中父親結(jié)點(diǎn)與其孩子結(jié)點(diǎn)所蘊(yùn)含的邏輯關(guān)系，設(shè)計(jì)了一種有效的后置處理技術(shù)，該技術(shù)能夠有效地提高空間范圍查詢(xún)精度.

4) 理論分析了GT-R方法滿(mǎn)足ε-本地差分隱私，以及響應(yīng)范圍查詢(xún)的誤差邊界.通過(guò)真實(shí)數(shù)據(jù)實(shí)驗(yàn)分析，該方法具有較高可用性和空間范圍查詢(xún)準(zhǔn)確性.

1 相關(guān)工作

基于中心化差分隱私的空間范圍查詢(xún)已存在多種方法.文獻(xiàn)[1]利用均分網(wǎng)格自適應(yīng)地劃分2維空間數(shù)據(jù)，對(duì)單元格添加相應(yīng)的拉普拉斯噪音，然后結(jié)合噪音單元格響應(yīng)范圍查詢(xún)；文獻(xiàn)[2]采用kd-樹(shù)對(duì)2維空間數(shù)據(jù)進(jìn)行劃分，利用指數(shù)機(jī)制選擇分割中線以避免泄露實(shí)際空間點(diǎn)；文獻(xiàn)[3]結(jié)合完全四分樹(shù)劃分空間數(shù)據(jù)，并通過(guò)結(jié)點(diǎn)計(jì)數(shù)的偏移值來(lái)減少噪音.上述這些方法均是在假設(shè)數(shù)據(jù)收集者是可信的前提下才成立，不能直接應(yīng)用于本地差分隱私環(huán)境.此外，這些方法在進(jìn)行擾動(dòng)時(shí)常依賴(lài)于拉普拉斯機(jī)制與全局敏感度的大小.而拉普拉斯機(jī)制通常導(dǎo)致誤差很大的本地差分隱私統(tǒng)計(jì)結(jié)果.

目前本地差分隱私研究主要集中于頻率估計(jì)[4-5]、Heavy hitter[6]、均值估計(jì)[7-10]、頻繁模式挖掘[11]以及圖數(shù)據(jù)統(tǒng)計(jì)[12]等研究.而涉及空間范圍查詢(xún)的工作卻很少.文獻(xiàn)[5]結(jié)合隨機(jī)應(yīng)答與1元編碼提出了基本Rappor方法，該方法被嵌入谷歌Chrome平臺(tái)收集用戶(hù)的會(huì)話(huà)記錄，并估計(jì)會(huì)話(huà)項(xiàng)的頻率.然而，1元編碼無(wú)法應(yīng)對(duì)較大的值域d，通信代價(jià)為Θ(d).為此，文獻(xiàn)[5]利用布隆過(guò)濾把值域d散列到相對(duì)較小的值域中，通信代價(jià)為Θ(k).不同于文獻(xiàn)[5]，文獻(xiàn)[6]采用隨機(jī)矩陣投影技術(shù)對(duì)值域d進(jìn)行編碼，通訊代價(jià)為Θ(logm).此外，文獻(xiàn)[6]利用2元本地散列技術(shù)對(duì)值域d進(jìn)行編碼，其通信代價(jià)同樣為Θ(logd).為了取得更好的擾動(dòng)精度，文獻(xiàn)[7]結(jié)合1元編碼，提出了優(yōu)化1元編碼與優(yōu)化本地散列方法.盡管2種方法在較大的值域上取得同樣的精度，但本地散列的通信代價(jià)較小.

不同于上述方法中的頻率估計(jì)，文獻(xiàn)[8-10]集中研究均值估計(jì).文獻(xiàn)[8]結(jié)合隨機(jī)應(yīng)答機(jī)制估計(jì)連續(xù)區(qū)間[-1,1]中均值.而文獻(xiàn)[9]結(jié)合文獻(xiàn)[8]的高通信代價(jià)與計(jì)算代價(jià)，提出了高維數(shù)據(jù)上的均值估計(jì)方法.該方法取得較好的估計(jì)精度.然而文獻(xiàn)[8-9]方法的輸出是離散的，并且與輸入?yún)^(qū)間[-1,1]差別非常大.為此，文獻(xiàn)[10]結(jié)合文獻(xiàn)[8]與拉普拉斯機(jī)制的各自?xún)?yōu)點(diǎn)，提出了一種輸出為連續(xù)區(qū)間的譜方法，該方法能夠支持高維數(shù)據(jù)上的均值估計(jì)與SVM(support vector machines)分類(lèi).

上述的頻率與均值估計(jì)均無(wú)法直接應(yīng)用于空間范圍查詢(xún).近期文獻(xiàn)[13]結(jié)合完全2叉樹(shù)與Hadamard編碼響應(yīng)1維范圍查詢(xún)，然而由于索引結(jié)構(gòu)的不同，該方法無(wú)法直接應(yīng)用于空間范圍查詢(xún).文獻(xiàn)[14]提出了基于本地差分隱私的空間數(shù)據(jù)聚集方法，該方法結(jié)合用戶(hù)個(gè)性化隱私需求與分類(lèi)樹(shù)來(lái)分析所有用戶(hù)的位置分布.盡管該方法能夠響應(yīng)范圍查詢(xún)，但與本文的需求存在不同：文獻(xiàn)[14]中的層次結(jié)構(gòu)劃分空間數(shù)據(jù)只是在語(yǔ)義層面，缺少實(shí)際的空間索引結(jié)構(gòu).因此，針對(duì)上述方法的不足，本文提出了一種基于網(wǎng)格與四分樹(shù)結(jié)構(gòu)的空間范圍查詢(xún)方法，該方法不但能夠適應(yīng)于大規(guī)模空間數(shù)據(jù)，還能夠比較精確地響應(yīng)不同粒度的范圍查詢(xún).

2 定義與問(wèn)題

2.1 本地差分隱私

不同于中心化差分隱私保護(hù)技術(shù)，本地差分隱私技術(shù)通常要求用戶(hù)在本地保護(hù)自己的數(shù)據(jù)，把擾動(dòng)之后的數(shù)據(jù)報(bào)告給不可信的收集者，從而實(shí)現(xiàn)隱私不被泄露.本地差分隱私的形式化定義為:

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

Pr[A(l)∈O]≤exp(ε)×Pr[A(l′)∈O]，

(1)

其中ε為隱私預(yù)算，其值越小則算法A的隱私保護(hù)程度越高.

隨機(jī)應(yīng)答機(jī)制[15]與拉普拉斯機(jī)制[16]是實(shí)現(xiàn)本地差分隱私的常用技術(shù).拉普拉斯機(jī)制通常需要計(jì)算出某操作的全局敏感性，利用拉普拉斯分布生成噪音對(duì)用戶(hù)數(shù)值進(jìn)行擾動(dòng).不同于拉普拉斯機(jī)制，隨機(jī)應(yīng)答機(jī)制在用戶(hù)發(fā)送數(shù)據(jù)li之前，對(duì)其進(jìn)行隨機(jī)擾動(dòng).該機(jī)制的原始思想是用戶(hù)在響應(yīng)敏感的布爾問(wèn)題時(shí)，以概率p真實(shí)應(yīng)答，以1-p的概率給出相反的應(yīng)答.為了使隨機(jī)應(yīng)答機(jī)制滿(mǎn)足ε-本地差分隱私，通常設(shè)置p=exp(ε)(1+exp(ε))或者更大的值(例如12)，收集者獲得所有應(yīng)答后，即可對(duì)真實(shí)應(yīng)答進(jìn)行分析估計(jì).

2.2 空間數(shù)據(jù)范圍查詢(xún)

空間數(shù)據(jù)通常包括空間位置信息、空間軌跡信息等，以2維散點(diǎn)圖形式描述用戶(hù)的空間位置.而空間范圍查詢(xún)是指在某一范圍內(nèi)所包含的用戶(hù)位置個(gè)數(shù).設(shè)Dom(D)為空間數(shù)據(jù)集D的值域，li(xi,yi)表示第i個(gè)用戶(hù)的位置，其中xi與yi表示相應(yīng)的經(jīng)緯度.下面給出空間范圍查詢(xún)的形式化表示.

定義2.空間范圍查詢(xún).給定n個(gè)用戶(hù)與一個(gè)空間范圍查詢(xún)框Q(Q∈D)且Q=[a,b]×[c,d]，則Q的查詢(xún)結(jié)果可以表示為

(2)

其中，I是標(biāo)識(shí)函數(shù)，其值為1表示第i個(gè)用戶(hù)的空間位置在Q內(nèi)，其值為0表該用戶(hù)位置不在Q內(nèi).

2.3 問(wèn)題描述

3 基于本地差分隱私的空間范圍查詢(xún)方法

3.1 空間范圍查詢(xún)的原則

基于相關(guān)工作的分析，在設(shè)計(jì)新的基于本地差分隱私的空間范圍查詢(xún)方法時(shí)需要考慮2個(gè)原則：

1) 針對(duì)現(xiàn)有編碼機(jī)制無(wú)法直接應(yīng)對(duì)空間2維數(shù)據(jù)，所設(shè)計(jì)的方法盡可能利用空間幾何結(jié)構(gòu)對(duì)空間數(shù)據(jù)進(jìn)行分割與索引；

2) 針對(duì)現(xiàn)有只對(duì)單個(gè)點(diǎn)的頻率估計(jì)方法無(wú)法適應(yīng)于2維空間范圍查詢(xún)，所設(shè)計(jì)的方法盡量能夠保證較高的查詢(xún)精度.

針對(duì)原則1與原則2，本文利用網(wǎng)格與四分樹(shù)對(duì)大規(guī)?？臻g數(shù)據(jù)進(jìn)行分割與編碼，在此基礎(chǔ)上提出了一種有效的空間范圍查詢(xún)方法GT-R，該方法能夠滿(mǎn)足本地差分隱私且輸出較高精度的查詢(xún)結(jié)果.

3.2 基于整個(gè)空間值域的范圍查詢(xún)方法

給定n個(gè)用戶(hù)，每個(gè)用戶(hù)擁有自己的空間位置.設(shè)c(li)表示li(li∈Dom(D))的用戶(hù)計(jì)數(shù).則式(2)可以重新表示為

(3)

在響應(yīng)空間范圍查詢(xún)Q=[a,b] ×[c,d]時(shí)，最直接的方法是每個(gè)用戶(hù)按照空間位置所在的值域Dom(D)進(jìn)行2進(jìn)制編碼，結(jié)合隨機(jī)應(yīng)答機(jī)制擾動(dòng)2進(jìn)制編碼，收集者匯總Dom(D)中所有的位置后再響應(yīng)Q查詢(xún).假設(shè)error(A)表示某種隨機(jī)應(yīng)答機(jī)制A擾動(dòng)用戶(hù)位置所產(chǎn)生的誤差.則采用A直接響應(yīng)范圍查詢(xún)Q所產(chǎn)生的最壞誤差為

(4)

其中，(b-a)×(d-c)表示查詢(xún)框Q的面積.

響應(yīng)查詢(xún)Q的誤差隨著Q的面積呈線性增加.例如利用拉普拉斯機(jī)制報(bào)告每個(gè)位置并響應(yīng)查詢(xún)Q所產(chǎn)生的誤差為8(b-a)(d-c)nε2.由于直接方法是基于整個(gè)空間值域Dom(D)對(duì)用戶(hù)位置進(jìn)行編碼，過(guò)大的值域?qū)е路秶樵?xún)誤差與查詢(xún)框面積線性相關(guān).因此，本文基于網(wǎng)格劃分技術(shù)將空間值域分割成均勻單元格區(qū)域，將每個(gè)用戶(hù)的位置信息壓縮到一個(gè)單元格區(qū)域中.每個(gè)用戶(hù)結(jié)合單元格區(qū)域所構(gòu)建的四分樹(shù)對(duì)自身位置進(jìn)行編碼.收集者通過(guò)重構(gòu)四分樹(shù)來(lái)響應(yīng)空間范圍查詢(xún).

3.3 基于網(wǎng)格分割的空間范圍查詢(xún)方法

網(wǎng)格分割是空間劃分常用技術(shù)之一，其主要特點(diǎn)是在不涉及實(shí)際數(shù)據(jù)分布的情況下將空間分割成大小相等或不等的單元格區(qū)域.單元格區(qū)域是空間范圍查詢(xún)的最小響應(yīng)單元.

3.3.1 基于均勻網(wǎng)格的空間范圍查詢(xún)方法

本節(jié)首先基于均勻網(wǎng)格提出GT-R算法，該算法包括基于網(wǎng)格與四分樹(shù)結(jié)構(gòu)的空間劃分和索引、收集者重構(gòu)四分樹(shù)、用戶(hù)利用四分樹(shù)擾動(dòng)自身位置以及響應(yīng)查詢(xún)4種操作.該算法具體細(xì)節(jié)詳見(jiàn)算法1：

Fig. 2 Grid decomposition and quadtree index圖2 網(wǎng)格劃分與四分樹(shù)索引

用戶(hù)結(jié)合已被賦值的四分樹(shù)T，向收集者報(bào)告自己的空間位置.LRR算法詳見(jiàn)算法2：

收集者把空的四分樹(shù)T共享給用戶(hù)后，每個(gè)用戶(hù)均擁有一棵T的副本(算法1行③).結(jié)合LRR算法，用戶(hù)首先遍歷四分樹(shù)T，尋找到包含自身位置的路徑，并判斷自己的空間位置屬于T中哪個(gè)葉子結(jié)點(diǎn)(算法2行②)，找到所屬葉子結(jié)點(diǎn)之后，該葉子結(jié)點(diǎn)至根結(jié)點(diǎn)路徑的權(quán)重均被賦值為1，其他路徑的權(quán)重為0(算法2行③～⑨).例如給定用戶(hù)ui的空間位置li(xi=28,yi=12).ui結(jié)合圖2中的四分樹(shù)T，判斷l(xiāng)i(xi=28,yi=12)屬于結(jié)點(diǎn)v12([24,32]×[8,16])，則路徑v12-v3-v1上的權(quán)重均被賦值為1，如圖2所示.接下來(lái)每個(gè)用戶(hù)在T中隨機(jī)選擇一層，并產(chǎn)生由01構(gòu)成的向量(算法2行⑩).例如，隨機(jī)選擇圖2中四分樹(shù)的第2層，則所生成的向量為Vi=(0,1,0,0).最后利用優(yōu)化隨機(jī)應(yīng)答機(jī)制[7]生成報(bào)告結(jié)果(算法2行～).由于每個(gè)用戶(hù)在T中隨機(jī)選擇一層報(bào)告，則LRR算法最壞的通信代價(jià)為

定理2.LRR算法滿(mǎn)足ε-本地差分隱私.

則：

根據(jù)定義1可知，LRR算法滿(mǎn)足ε-本地差分隱私.

證畢.

盡管通過(guò)LRR算法可以重構(gòu)四分樹(shù)T，但我們期望T中每個(gè)結(jié)點(diǎn)的噪音計(jì)數(shù)滿(mǎn)足無(wú)偏性.

定理3.假設(shè)vi是收集者重構(gòu)四分樹(shù)T中的任意結(jié)點(diǎn)，c(vi)與c′(vi)分別是結(jié)點(diǎn)vi中真實(shí)的用戶(hù)位置數(shù)與估計(jì)數(shù)，則無(wú)偏估計(jì)E[c′(vi)]=c(vi)成立.

證明. 設(shè)l為結(jié)點(diǎn)vi所在的層次，nl為該層次中的用戶(hù)數(shù)，也是結(jié)點(diǎn)vi中的用戶(hù)報(bào)告數(shù)目.根據(jù)算法1的行c′(vi)=c′(vi)+zi可知，nl個(gè)用戶(hù)把自己的位置信息匯總到l層每個(gè)結(jié)點(diǎn)中去.設(shè)I(vi)表示結(jié)點(diǎn)vi中1的個(gè)數(shù).為了證明方便，結(jié)合算法2設(shè)Pr[zi=1|wi(vj)]=p，以概率p生成zi=1，否則以概率Pr[zi=0|wi(vj)]=q生成zi=0.則I(vi)=p×c′(vi)+q×(nl-c′(vi))成立.進(jìn)而可以獲得隨機(jī)變量c′(vi):

則:

成立.

根據(jù)I(vi)=p×c′(vi)+q×(nl-c′(vi))可知:

我們期望E[c′(vi)]=c(vi)，則:

成立.

證畢.

由于每個(gè)用戶(hù)本地?cái)_動(dòng)自身的空間位置，T中每個(gè)結(jié)點(diǎn)的計(jì)數(shù)不可避免地產(chǎn)生誤差.定理4給出了每個(gè)結(jié)點(diǎn)所產(chǎn)生的方差.

定理4.假設(shè)vi是收集者重構(gòu)四分樹(shù)T中的任意結(jié)點(diǎn)，nl為l層次中的用戶(hù)數(shù)，p=12，q=1(1+exp(ε))，c(vi)與c′(vi)分別是結(jié)點(diǎn)vi中真實(shí)的用戶(hù)位置數(shù)與估計(jì)數(shù)，則:

證畢.

由文獻(xiàn)[12]可知，T中很多結(jié)點(diǎn)真實(shí)位置計(jì)數(shù)非常小，因此，Var[c′(vi)]≈nl×4×exp(ε)(exp(ε)-1)2.進(jìn)而可知每個(gè)結(jié)點(diǎn)的方差僅與四分樹(shù)每層所分配的用戶(hù)個(gè)數(shù)nl線性相關(guān).

盡管通過(guò)定理4可以估算出每個(gè)結(jié)點(diǎn)產(chǎn)生的方差，而如何度量c(vi)與c′(vi)之間的最大偏差是個(gè)挑戰(zhàn)性問(wèn)題.

定理5.假設(shè)vi是收集者重構(gòu)四分樹(shù)T中的任意結(jié)點(diǎn)，設(shè)lj是第j個(gè)用戶(hù)的位置.c(vi)與c′(vi)分別是結(jié)點(diǎn)vi中真實(shí)的用戶(hù)位置數(shù)與估計(jì)數(shù)，則等式至少以概率1-β成立:

其中,n為用戶(hù)個(gè)數(shù)，?=1+2log4m為四分樹(shù)高度.

證明. 設(shè)c′(vi)-c(vi)為一個(gè)隨機(jī)變量，根據(jù)定理3可知其均值為0.根據(jù)算法1與算法2可知：

(5)

其中，wj(vi)與zj分別表示第j個(gè)用戶(hù)的真實(shí)值與估計(jì)值.

同理可知zj-wj(vi)也是一個(gè)隨機(jī)變量.由于zj∈{0,1}，wj(vi)∈{0,1}，則zj-wj(vi)∈{-1,0,1}.

隨機(jī)變量zj-wj(vi)的方差可以表示為

此外，由式(5)可知:

|zj-wj(vi)|≤2(exp(ε)+1)(exp(ε)-1)

成立.根據(jù)Bernstein不等式可知:

證畢.

結(jié)合收集者重構(gòu)的四分樹(shù)T響應(yīng)空間范圍查詢(xún)Q，具體細(xì)節(jié)如算法3描述.

收集者利用GT-R算法重構(gòu)四分樹(shù)T之后，首先進(jìn)行后置處理(行①)，再利用TDT算法自動(dòng)向下遍歷T即可響應(yīng)空間范圍查詢(xún)Q.如果某結(jié)點(diǎn)與Q無(wú)交叉，則忽略該結(jié)點(diǎn)(行⑤⑥).若Q完全包含該結(jié)點(diǎn)，即可把該結(jié)點(diǎn)中的空間點(diǎn)數(shù)添加響應(yīng)結(jié)果中(行⑦⑧).若Q部分包含該結(jié)點(diǎn)且該結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則重新遍歷該結(jié)點(diǎn)的孩子結(jié)點(diǎn)(行⑨～).否則計(jì)算Q與該結(jié)點(diǎn)的重合部分，并把重合部分中的空間點(diǎn)數(shù)添加響應(yīng)結(jié)果中(行～).

定理6.結(jié)合算法1與算法3，任意空間范圍查詢(xún)Q的最大誤差error(Q)滿(mǎn)足：

其中，η為某一常數(shù).

結(jié)合Var[c′(vi)]≈nl×4×exp(ε)(exp(ε)-1)2，可知不等式成立：

(6)

基于目標(biāo)函數(shù)min(f)與柯西-施瓦茨不等式可知不等式成立:

(7)

當(dāng)nl=η×2?-l×nl時(shí)，則不等式(7)中的等號(hào)成立.可知2?-l=1η.該等式說(shuō)明四分樹(shù)中響應(yīng)查詢(xún)Q的結(jié)點(diǎn)個(gè)數(shù)是定值,則min(f)=nη.進(jìn)而可知:

證畢.

結(jié)合定理6與式(4)可知，GT-R算法與最直接方法均可以采用方差度量誤差.若在最直接方法中每個(gè)用戶(hù)也利用優(yōu)化隨機(jī)應(yīng)答機(jī)制擾動(dòng)自身位置，可知error(A)=4n×exp(ε)(exp(ε)-1)2.因此，只要范圍查詢(xún)Q的查詢(xún)面積大于8η，即可知GT-R算法優(yōu)于最直接方法.

3.3.2 基于重構(gòu)四分樹(shù)的求精處理方法

1) 自底向上的平均化處理

其中，uj表示結(jié)點(diǎn)vi的孩子結(jié)點(diǎn).

2) 自頂向下的均值一致性處理

其中，p(vi)表示結(jié)點(diǎn)vi的父親結(jié)點(diǎn).

結(jié)合圖2，以例子說(shuō)明求精處理過(guò)程.給定只有2層的四分樹(shù)T，vi為其根結(jié)點(diǎn).假設(shè)c′(vi)=5，其孩子結(jié)點(diǎn)的計(jì)數(shù)分別為c′(u1)=2，c′(u2)=1，c′(u3)=1，c′(u4)=2.由于c′(vi)≠c′(u1)+c′(u2)+c′(u3)+c′(u4)，則需要求精處理.處理之后c′(vi)=3.9，c′(u1)=2，c′(u2)=1，c′(u3)=1，c′(u4)=2.

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

實(shí)驗(yàn)平臺(tái)是4核Intel i7-4790 CPU(4 GHz)、8 GB內(nèi)存、Win7系統(tǒng).所有算法均采用Python實(shí)現(xiàn).實(shí)驗(yàn)采用2個(gè)數(shù)據(jù)集Checkin與Landmark，其中Checkin數(shù)據(jù)集從基于地理位置的社交網(wǎng)站Gowalla獲取，該數(shù)據(jù)集記錄了在2009-02—2010-10期間，Gowalla用戶(hù)簽到的時(shí)間和位置信息，包含100萬(wàn)條記錄；Landmark數(shù)據(jù)集從infochimps平臺(tái)獲得，該數(shù)據(jù)集記錄了2010年人口普查時(shí)用戶(hù)到過(guò)的美國(guó)48個(gè)州的地標(biāo)位置，總共包含87萬(wàn)條數(shù)據(jù).2種數(shù)據(jù)集具體細(xì)節(jié)與可視化結(jié)果分別如表1與圖3所示.

結(jié)合上述數(shù)據(jù)集，采用相對(duì)誤差(relative error,RE)度量 KRR[19]，RAPPOR[5]，PSDA[14]，OUE[7]，GT-R，N-PSDA，N-GT-R，QT-RAPPOR，QT-KRR方法的范圍查詢(xún)精度.其中N-PSDA與N-GT-R表示無(wú)空間結(jié)構(gòu)索引下的方法；QT-RAPPOR與QT-KRR表示四分樹(shù)索引下的RAPPOR與KRR方法.RE的表示為

(8)

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

本文設(shè)置的隱私預(yù)算參數(shù)ε的取值為0.1，0.3，0.5，0.7，0.9.實(shí)驗(yàn)中范圍查詢(xún)Q的查詢(xún)范圍分別覆蓋Landmark與Checkin這2種數(shù)據(jù)集的[10%,50%]，[15%,55%]，[20%,60%]，在每種查詢(xún)范圍內(nèi)隨機(jī)生成500次查詢(xún).

1) 基于Landmark數(shù)據(jù)集的多種方法RE值比較

圖4(a)～(f)描述了KRR，RAPPOR，OUE，N-PSDA以及N-GT-R算法的RE值比較結(jié)果.由圖4(a)～(c)的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，當(dāng)范圍查詢(xún)Q固定時(shí)，ε從0.1變化到0.9，5種方法的RE值均減少.然而，N-GT-R的范圍查詢(xún)精度優(yōu)于其他4種方法.在ε=0.7，Q為[15%,55%]時(shí)，N-GT-R所取得的查詢(xún)精度遠(yuǎn)優(yōu)于KRR方法和RAPPOR方法，從實(shí)驗(yàn)結(jié)果可以看出，其精度是KRR方法的近3倍，是RAPPOR方法的2倍多，是N-PSDA與OUE方法的近1倍.從圖4(d)～(f)的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，當(dāng)ε固定，Q的范圍從[5%,45%]變化到[20%,60%]時(shí)，5種方法的RE值均增大，其原因在于范圍查詢(xún)的查詢(xún)范圍越大，包含的查詢(xún)單個(gè)點(diǎn)數(shù)越多，累計(jì)誤差越大，導(dǎo)致精度隨著查詢(xún)范圍的增大而降低.從圖4(d)～(f)中還可以發(fā)現(xiàn)N-GT-R方法的精度優(yōu)于其他4種方法，其原因在于N-GT-R算法采用均勻網(wǎng)格分割整個(gè)值域，縮小了值域空間.

圖4(g)～(l)描述了QT-KRR，QT-RAPPOR，PSDA，GT-R 這4種方法的RE值比較結(jié)果.由圖4(g)～ (i)可以發(fā)現(xiàn)，當(dāng)范圍查詢(xún)Q固定時(shí)，ε從0.1變化到0.9，4種方法的RE值均減少，且GT-R方法明顯優(yōu)于其他3種方法.當(dāng)ε=0.5且Q為[20%,60%]時(shí)，GT-R所取得的精度是QT-RAPPOR的近4倍，是QT-KRR和PSDA的近3倍.其原因是GT-R方法采用均勻網(wǎng)格與四分樹(shù)對(duì)空間值域進(jìn)行重新編碼與索引，而其他3種方法均是基于整個(gè)值域響應(yīng)范圍查詢(xún).此外，GT-R通過(guò)后置處理使結(jié)果不僅達(dá)到了無(wú)偏還保證了結(jié)果的一致性.由圖4(j)～(l)還發(fā)現(xiàn)，當(dāng)固定ε，查詢(xún)范圍Q從[5%,45%]變化到[15%,55%]時(shí)，4種方法的查詢(xún)精度隨著查詢(xún)范圍的增大而降低.但查詢(xún)范圍Q從[15%,55%]變化到[20%,60%]時(shí)，4種方法的查詢(xún)精度出現(xiàn)隨著查詢(xún)范圍的增大而提高的現(xiàn)象，其原因在于使用四分樹(shù)索引后，Q的查詢(xún)精度與其所含蓋的樹(shù)中結(jié)點(diǎn)個(gè)數(shù)成反比，隨著查詢(xún)面積的增大，查詢(xún)范圍在四分樹(shù)中含蓋的索引結(jié)點(diǎn)個(gè)數(shù)可能變少，反而使精度更加精準(zhǔn).

Fig. 4 Results of range queries on Landmark圖4 Landmark數(shù)據(jù)集范圍查詢(xún)結(jié)果

2) 基于Checkin數(shù)據(jù)集的多種方法RE值比較

圖5(a)～(f)描述了KRR，RAPPOR，OUE，N-PSDA，N-GT-R 這5種方法的RE值比較結(jié)果.由圖5(a)～(f)可以發(fā)現(xiàn)，當(dāng)范圍查詢(xún)Q固定，ε從0.1變化到0.9時(shí)，5種方法的RE值均減少，然而N-GT-R的查詢(xún)誤差的穩(wěn)定性與查詢(xún)精度優(yōu)于其他5種方法.當(dāng)ε=0.3且查詢(xún)范圍為[15%,55%]時(shí)，N-GT-R方法所取得的查詢(xún)精度是KRR方法的近4倍，是RAPPOR方法的近3倍，是OUE方法和N-PSDA的近0.5倍.當(dāng)ε固定，隨著查詢(xún)范圍擴(kuò)大，5種方法查詢(xún)精度均呈現(xiàn)下降趨勢(shì)，但N-GT-R方法的查詢(xún)精度與誤差穩(wěn)定性同樣優(yōu)于其他4種方法.其主要原因是N-GT-R方法減小了值域空間，在做相同的范圍查詢(xún)時(shí)比其他方法所累積的誤差少.

Fig. 5 Results of range queries on Checkin圖5 Checkin數(shù)據(jù)集范圍查詢(xún)結(jié)果

圖5(g)～(l)描述了QT-KRR，QT-RAPPOR，PSDA，GT-R 這4種方法的RE值比較結(jié)果.由圖5(g)～(i)可知，當(dāng)范圍查詢(xún)Q固定且ε增大時(shí)，4種方法的誤差均減小.特別是查詢(xún)范圍為[10%,50%]且ε=0.9時(shí)，GT-R方法的精度是PSDA方法和QT-RAPPOR方法的近7倍，是QT-KRR的近6倍.此外，由圖5(j)～(l)顯示，當(dāng)ε固定，查詢(xún)范圍Q從[5%,45%]變化到[20%,60%]時(shí)，GT-R方法在各個(gè)范圍的查詢(xún)精度雖然變化相對(duì)不大，但優(yōu)于其他3種方法.在ε=0.5時(shí)，GT-R方法取得的精度是其他3種方法的1倍以上.其主要原因是GT-R方法利用網(wǎng)格與四分樹(shù)對(duì)整個(gè)空間值域進(jìn)行壓縮與重新編碼，既縮減了值域空間又減少了統(tǒng)計(jì)時(shí)的累計(jì)誤差點(diǎn)數(shù)，因此精度優(yōu)于其他方法.

5 結(jié)束語(yǔ)

針對(duì)本地差分隱私保護(hù)下收集用戶(hù)空間位置存在的問(wèn)題，本文結(jié)合現(xiàn)有的用戶(hù)數(shù)據(jù)收集方法存在的不足，提出了基于網(wǎng)格與四分樹(shù)索引的空間位置收集方法GT-R.該方法通過(guò)均勻網(wǎng)格縮小空間值域，通過(guò)四分樹(shù)對(duì)用戶(hù)位置進(jìn)行重新編碼.從本地差分隱私定義角度分析GT-R滿(mǎn)足ε-本地差分隱私.最后通過(guò)2種真實(shí)的大規(guī)模數(shù)據(jù)集驗(yàn)證了GT-R方法的范圍查詢(xún)精度.實(shí)驗(yàn)結(jié)果表明：GT-R明顯優(yōu)于現(xiàn)有的同類(lèi)方法.未來(lái)工作考慮動(dòng)態(tài)環(huán)境下的隱私空間數(shù)據(jù)收集與分析問(wèn)題.