金凱忠，張嘯劍+，彭慧麗,2

1.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，鄭州 450046

2.河南廣播電視大學(xué)，鄭州 450008

KD-TSS：精確隱私空間分割方法*

金凱忠1，張嘯劍1+，彭慧麗1,2

1.河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，鄭州 450046

2.河南廣播電視大學(xué)，鄭州 450008

Abstract:KD-Tree-based differentially private spatial decomposition has attracted considerable research attention in recent years.The trade-off between the size of spatial data and Laplace noise directly constrains the accuracy of decomposition.This paper proposes a straightforward method with differential privacy,called SKD-TS(samplingbased KD-Tree)to partition spatial data.To handle the large-scale spatial data,this method employs Bernoulli random sampling technology to obtain the samples.While SKD-Tree still relies on the height of KD-Tree to control the Laplace noise.However,the choice of the height is a serious subtitle:a large height makes excessive noise in the nodes,while a small height leads to the partition too coarse-grained.To remedy the deficiency of SKD-Tree,this paper proposes another method,called KD-TSS(KD-Tree with sampling and SVT)for spatial decomposition.The sparsevector technology(SVT)is used in KD-TSS to judge whether a node of KD-Tree should be split,without depending on the height.SKD-TS and KD-TSS methods are compared with existing methods such as KD-Stand,KD-Hybird on the large-scale real datasets.The experimental results show that the two algorithms outperform their competitors,achieve the accurate decomposition and results of range query.

Key words:differential privacy;KD-Tree;private spatial decomposition;Bernoulli random sampling;sparse vector technology

基于KD-樹(shù)與差分隱私保護(hù)的空間數(shù)據(jù)分割得到了研究者的廣泛關(guān)注，空間數(shù)據(jù)的大小與拉普拉斯噪音的多少直接制約著空間分割的精度。針對(duì)現(xiàn)有基于KD-樹(shù)分割方法難以有效兼顧大規(guī)?？臻g數(shù)據(jù)與噪音量不足的問(wèn)題，提出了一種滿(mǎn)足差分隱私的KD-樹(shù)分割方法SKD-Tree（sampling-based KD-Tree）。該方法利用滿(mǎn)足差分隱私的伯努利隨機(jī)抽樣技術(shù)，抽取空間樣本作為分割對(duì)象，然而卻沒(méi)有擺脫利用樹(shù)高度控制拉普拉斯噪音。啟發(fā)式設(shè)定合適的樹(shù)高度非常困難，樹(shù)高度過(guò)大，導(dǎo)致結(jié)點(diǎn)的噪音值過(guò)大；樹(shù)高度過(guò)小，導(dǎo)致空間分割粒度太粗劣。為了彌補(bǔ)SKD-Tree方法的不足，提出了一種基于稀疏向量技術(shù)（sparse vector technology，SVT）的空間分割方法KD-TSS（KD-Tree with sampling and SVT）。該方法通過(guò)SVT判斷樹(shù)中結(jié)點(diǎn)是否繼續(xù)分割，不再依賴(lài)KD-樹(shù)高度來(lái)控制結(jié)點(diǎn)中的噪音值。SKD-Tree、KD-TSS與KD-Stand、KD-Hybrid在真實(shí)的大規(guī)?？臻g數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果表明，其分割精度以及響應(yīng)范圍查詢(xún)效果優(yōu)于同類(lèi)算法。

差分隱私；KD-樹(shù)；隱私空間劃分；伯努利隨機(jī)抽樣；稀疏向量技術(shù)

1 引言

信息時(shí)代的飛速發(fā)展，空間數(shù)據(jù)的獲取與收集變得尤為容易，例如移動(dòng)用戶(hù)位置、GPS位置、家庭住址等數(shù)據(jù)。通過(guò)對(duì)空間數(shù)據(jù)的分析，使得交通監(jiān)控、位置推薦等應(yīng)用能夠提高自身的服務(wù)質(zhì)量。然而，空間數(shù)據(jù)蘊(yùn)含著豐富的個(gè)人敏感信息，在提供給第三方應(yīng)用的同時(shí)，個(gè)人的敏感信息有可能被泄露。因此，如何在隱私保護(hù)的前提下，發(fā)布空間數(shù)據(jù)是當(dāng)前基于位置服務(wù)的主要挑戰(zhàn)問(wèn)題。匿名化[1]與差分隱私[2-4]是常用的隱私保護(hù)模型。然而，匿名模型由于對(duì)攻擊背景知識(shí)與攻擊模型給出過(guò)多特定假設(shè)，而不適合真實(shí)的位置服務(wù)。例如，文獻(xiàn)[5]指出針對(duì)150萬(wàn)條匿名后的用戶(hù)位置數(shù)據(jù)，在無(wú)任何背景假設(shè)情況下，隨機(jī)給出2個(gè)時(shí)空點(diǎn)，能夠甄別出50%用戶(hù)的敏感位置，隨機(jī)給出4個(gè)時(shí)空點(diǎn)，能夠甄別出97%用戶(hù)的敏感位置。不同于傳統(tǒng)的匿名化模型，差分隱私模型要求數(shù)據(jù)庫(kù)中任何一個(gè)用戶(hù)的存在都不應(yīng)顯著地改變?nèi)魏尾樵?xún)的結(jié)果，從而保證了每個(gè)用戶(hù)加入該數(shù)據(jù)庫(kù)不會(huì)對(duì)其隱私造成危險(xiǎn)。

近年來(lái)，出現(xiàn)了幾種滿(mǎn)足差分隱私的KD-樹(shù)空間劃分方法。HKD-Tree（hierarchical KD-tree）[6]是此類(lèi)方法的早期代表。該方法利用部分隱私代價(jià)對(duì)原始空間數(shù)據(jù)進(jìn)行網(wǎng)格劃分，然后基于網(wǎng)格的每個(gè)劃分單元構(gòu)建KD-樹(shù)。然而，該方法沒(méi)有從數(shù)據(jù)相關(guān)（data dependent）的角度考慮空間數(shù)據(jù)的實(shí)際分布與大小，KD-樹(shù)僅起到索引作用。文獻(xiàn)[7]是最早從數(shù)據(jù)相關(guān)角度分割空間數(shù)據(jù)的，并給出KD-Stand與KD-Hybrid兩種方法。KD-Stand方法利用指數(shù)機(jī)制[8]尋找每次分割的中位數(shù)（例如圖1中的a點(diǎn)），KD-Hybrid結(jié)合四分樹(shù)與KD-樹(shù)達(dá)到比較理想的分割效果。上述幾種方法均采用KD-樹(shù)對(duì)空間數(shù)據(jù)進(jìn)行分割，然而這些方法存在以下問(wèn)題。

Fig.1 Spatial decomposition with KD-Tree圖1 基于KD-樹(shù)的空間分割

問(wèn)題1 HKD-Tree、KD-Stand以及KD-Hybrid方法僅僅在小的空間數(shù)據(jù)上進(jìn)行分割，支持相應(yīng)的范圍查詢(xún)。然而，當(dāng)數(shù)據(jù)點(diǎn)達(dá)到百萬(wàn)級(jí)別時(shí)，這些方法的分割與響應(yīng)查詢(xún)精度很低。

問(wèn)題2 HKD-Tree、KD-Stand以及KD-Hybrid方法通常逐層分配隱私代價(jià)（例如ε/h，h為KD-樹(shù)的高度），然后利用結(jié)點(diǎn)中的噪音值判斷該結(jié)點(diǎn)是否繼續(xù)分割（例如判斷圖1中Q查詢(xún)的結(jié)果4+Lap(λ)≥θ是否成立，其中θ為分割閾值，λ≥ε/h）。然而，當(dāng)h很大時(shí)，KD-樹(shù)的分割精度會(huì)急劇降低。

總而言之，目前還沒(méi)有一個(gè)行之有效的方法同時(shí)克服上述兩種差分隱私下KD-樹(shù)分割空間數(shù)據(jù)的不足。為此，本文提出了兩種融合抽樣與稀疏向量技術(shù)（sparse vector technology，SVT）的KD-樹(shù)分割方法，在滿(mǎn)足差分隱私的情況下，采用伯努利抽樣技術(shù)對(duì)大規(guī)模原始空間數(shù)據(jù)進(jìn)行抽樣，在構(gòu)建KD-樹(shù)分割過(guò)程中，利用稀疏向量技術(shù)判斷結(jié)點(diǎn)是否繼續(xù)分割，實(shí)現(xiàn)高質(zhì)量的空間數(shù)據(jù)發(fā)布。

本文主要貢獻(xiàn)如下：

（1）為了解決問(wèn)題1，提出了SKD-Tree（samplingbased KD-Tree）方法，該方法利用伯努利抽樣技術(shù)對(duì)海量空間數(shù)據(jù)進(jìn)行抽樣，不但滿(mǎn)足差分隱私需求，而且能夠比較精確地響應(yīng)范圍查詢(xún)。

（2）為了有效解決問(wèn)題2，提出了KD-TSS（KDTree with sampling and SVT）方法，該方法利用抽樣與稀疏向量技術(shù)對(duì)KD-樹(shù)中結(jié)點(diǎn)進(jìn)行分割判斷，不再按照KD-樹(shù)的高度逐層分配隱私代價(jià)，進(jìn)而減少結(jié)點(diǎn)分割誤差，提升了葉子結(jié)點(diǎn)中計(jì)數(shù)值的發(fā)布精度。

（3）理論分析了SKD-Tree與KD-TSS方法滿(mǎn)足ε-差分隱私，通過(guò)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)分析展示了兩種方法在兼顧高可用性和準(zhǔn)確性的同時(shí)，優(yōu)于同類(lèi)方法。

2 相關(guān)工作

差分隱私擁有極強(qiáng)的保護(hù)能力，并依賴(lài)嚴(yán)謹(jǐn)?shù)慕y(tǒng)計(jì)模型，這些特點(diǎn)使其得到廣泛研究和應(yīng)用。當(dāng)前學(xué)術(shù)界的應(yīng)用著重關(guān)注差分隱私保護(hù)下的直方圖發(fā)布[9]、高維數(shù)據(jù)發(fā)布[10-11]等。鑒于空間數(shù)據(jù)在分析應(yīng)用中的重要性，研究者已經(jīng)提出了多種基于差分隱私的空間數(shù)據(jù)分割方法。HKD-Tree[6]是空間數(shù)據(jù)分割的早期代表，該方法利用網(wǎng)格分割原始數(shù)據(jù)，并為每個(gè)網(wǎng)格單元添加噪音，利用KD-樹(shù)進(jìn)行索引，其只有在數(shù)據(jù)均勻分布的前提下才有效。Quad-post[7]利用四分樹(shù)與后置處理技術(shù)發(fā)布空間數(shù)據(jù)，該方法同樣沒(méi)有考慮原始數(shù)據(jù)分布，僅對(duì)葉子結(jié)點(diǎn)中計(jì)數(shù)添加相應(yīng)的噪音。HKD-Tree與Quad-post通常利用樹(shù)的高度控制噪音大小，然而PrivTree[12]在添加噪音時(shí)，不依賴(lài)于樹(shù)高度，該方法利用一個(gè)噪音常量來(lái)判斷某個(gè)結(jié)點(diǎn)是否分割。網(wǎng)格也是空間數(shù)據(jù)分割常用的數(shù)據(jù)結(jié)構(gòu)。UG（uniform grid）[13]采用均勻網(wǎng)格劃分二維空間數(shù)據(jù)，并為每個(gè)劃分單元添加噪音，然而該方法無(wú)法顧及原始數(shù)據(jù)分布的偏斜問(wèn)題。針對(duì)UG方法的不足，AG（adaptive grid）[13]根據(jù)高層劃分單元的粒度不同，自適應(yīng)地自頂向下劃分，然而該方法同樣沒(méi)有考慮原始數(shù)據(jù)的實(shí)際分布。

上述方法大都屬于數(shù)據(jù)無(wú)關(guān)（data independent）的方法，這類(lèi)方法通常不考慮原始數(shù)據(jù)分布，其優(yōu)勢(shì)在于能夠給出嚴(yán)謹(jǐn)?shù)臄?shù)據(jù)效用理論下限。但在實(shí)際數(shù)據(jù)上，這一系列方法均無(wú)法獲得理想的數(shù)據(jù)可用性和效率，從而引出了數(shù)據(jù)相關(guān)方法的研究。所有空間數(shù)據(jù)相關(guān)的研究中最有希望的當(dāng)屬基于KD-樹(shù)的分割方法。KD-Stand[7]利用指數(shù)機(jī)制分割中位數(shù)，以免泄露實(shí)際的數(shù)據(jù)點(diǎn)，并利用結(jié)點(diǎn)中的噪音計(jì)數(shù)與給定的閾值相比較，來(lái)判斷該結(jié)點(diǎn)是否繼續(xù)分割。不同于KD-Stand，KD-Hybrid[7]首先利用四分樹(shù)分割部分原始數(shù)據(jù)，然后再利用KD-樹(shù)分割剩余數(shù)據(jù)。然而，KD-Stand與KD-Hybrid兩種方法具有相同的不足之處，二者均采用啟發(fā)式設(shè)定樹(shù)的高度來(lái)控制結(jié)點(diǎn)中的噪音量。而樹(shù)的高度通常無(wú)法具體設(shè)定，樹(shù)高度太小，導(dǎo)致空間數(shù)據(jù)分割粒度太粗劣；樹(shù)高度太大，導(dǎo)致葉子結(jié)點(diǎn)中的噪音值過(guò)大，影響最終的范圍查詢(xún)精度。此外，KD-Stand與KD-Hybrid兩種方法很難應(yīng)對(duì)大規(guī)?？臻g數(shù)據(jù)。因此，本文針對(duì)上述數(shù)據(jù)相關(guān)方法的不足，提出了兩種基于抽樣的空間分割方法KD-TSS與SKD-Tree，其中KD-TSS方法不依賴(lài)于樹(shù)高度來(lái)控制噪音的大小。針對(duì)大的空間數(shù)據(jù)集，KD-TSS與SKD-Tree能夠比較精確地進(jìn)行范圍查詢(xún)。

3 定義與問(wèn)題

3.1 差分隱私

傳統(tǒng)的隱私保護(hù)模型如k-匿名[1]通常對(duì)攻擊背景知識(shí)與攻擊模型給出特定的假設(shè)，而現(xiàn)實(shí)中這些假設(shè)并不成立。相比于傳統(tǒng)保護(hù)模型，差分隱私保護(hù)模型具有兩個(gè)顯著的特點(diǎn)：（1）不依賴(lài)于攻擊者的背景知識(shí)；（2）具有嚴(yán)謹(jǐn)?shù)慕y(tǒng)計(jì)學(xué)模型，能夠提供可量化的隱私保證。本文所關(guān)心的是在分割空間數(shù)據(jù)時(shí)，如何使得空間分割過(guò)程滿(mǎn)足差分隱私。

定義1（近鄰關(guān)系）設(shè)D={d1,d2,…,dn}為原始空間數(shù)據(jù)點(diǎn)，D′={d1,d2,…,dr-1,dr+1,…,dn}，D與D′相差一個(gè)數(shù)據(jù)點(diǎn)，則二者互為近鄰關(guān)系。

結(jié)合D與D′給出ε-差分隱私的形式化定義，如定義2所示。

定義2（ε-差分隱私）給定一個(gè)空間數(shù)據(jù)分割方法A，Range(A)為A的輸出范圍，若方法A在D與D′上任意分割結(jié)果T(T∈Range(A))滿(mǎn)足下列不等式，則A滿(mǎn)足ε-差分隱私：

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

從定義2可以看出，ε-差分隱私限制了任意一個(gè)記錄對(duì)方法A輸出結(jié)果的影響。實(shí)現(xiàn)差分隱私保護(hù)需要噪音機(jī)制的介入，拉普拉斯與指數(shù)機(jī)制是實(shí)現(xiàn)差分隱私的主要技術(shù)。所需要的噪音大小與其響應(yīng)查詢(xún)函數(shù)f的全局敏感性密切相關(guān)。

定義3（全局敏感性）設(shè)f為某一個(gè)查詢(xún)，且f:D→Rd，f的全局敏感性為：

其中，R為映射的實(shí)數(shù)空間；d為f的查詢(xún)維度。

文獻(xiàn)[2]提出的拉普拉斯機(jī)制可以取得差分隱私保護(hù)效果。該機(jī)制利用拉普拉斯分布產(chǎn)生噪音，進(jìn)而使得發(fā)布方法滿(mǎn)足ε-差異隱私，如定理1所示。

定理1[2]設(shè)f為某一個(gè)查詢(xún)函數(shù)，且f:D→Rn，若方法A符合下列等式，則A滿(mǎn)足ε-差異隱私：

其中，Lap(Δf/ε)為相互獨(dú)立的拉普拉斯噪音變量，噪音量大小與Δf成正比，與ε成反比。因此，查詢(xún)f的全局敏感性越大，所需的噪音越多。

文獻(xiàn)[8]提出的指數(shù)機(jī)制主要處理抽樣算法的輸出為非數(shù)值型的結(jié)果。該機(jī)制的關(guān)鍵技術(shù)是如何設(shè)計(jì)打分函數(shù)u(D,di)。設(shè)A為指數(shù)機(jī)制下的某個(gè)隱私方法，則A在打分函數(shù)作用下的輸出結(jié)果為：

其中，Δu為打分函數(shù)u(D,di)的全局敏感性；Ω為采用算法的輸出域。由該公式可知，di的打分函數(shù)越高，被選擇輸出的概率越大。

定理2[8]對(duì)于任意一個(gè)指數(shù)機(jī)制下的方法A，若A滿(mǎn)足式（4），則A滿(mǎn)足ε-差分隱私。

3.2 范圍查詢(xún)誤差

給定一個(gè)原始二維空間數(shù)據(jù)集D={d1,d2,…,dn}，每個(gè)di為一個(gè)二維數(shù)據(jù)點(diǎn)?；贒進(jìn)行KD-樹(shù)分割，得到滿(mǎn)足差分隱私的分割結(jié)果T。本文的問(wèn)題是如何針對(duì)T進(jìn)行比較精確的范圍查詢(xún)。而在響應(yīng)范圍查詢(xún)時(shí)，兩種誤差無(wú)法避免：一是采樣本身帶來(lái)的誤差（sampling error，SE）；二是結(jié)點(diǎn)中的拉普拉斯誤差（Laplace error，LE）。給定一個(gè)范圍查詢(xún)Q，假設(shè)有q個(gè)數(shù)據(jù)點(diǎn)落入Q查詢(xún)，則Q攜帶的誤差如式（5）所示：

本文采用與文獻(xiàn)[14]相同的方法，利用均方差來(lái)度量伯努利采樣誤差。設(shè)參數(shù)γ為抽樣概率，則SE(Q)=q(1-γ)/γ。利用拉普拉斯分布的方差度量拉普拉斯噪音誤差，則LE(Q)=2q(h/ε)2，其中h為KD-樹(shù)的高度，進(jìn)而使得Error(Q)=q(1-γ)/γ+2q(h/ε)2。

因此，如何使得Error(Q)盡量小是本文研究的重點(diǎn)。文獻(xiàn)[6-7]采用啟發(fā)式設(shè)置KD-樹(shù)的高度h達(dá)到控制范圍查詢(xún)誤差作用。而本文通過(guò)稀疏向量技術(shù)避免了拉普拉斯噪音對(duì)樹(shù)高度h的依賴(lài)。

4 基于KD-樹(shù)的空間分割方法

4.1 空間分割的原則

基于相關(guān)工作部分的分析，在設(shè)計(jì)新的基于KD-樹(shù)空間分割方法時(shí)需要考慮如下原則：

原則1針對(duì)大規(guī)?？臻g數(shù)據(jù)問(wèn)題，所設(shè)計(jì)的分割方法應(yīng)在滿(mǎn)足差分隱私條件下盡量抽取充足數(shù)據(jù)點(diǎn)作為分割對(duì)象。

原則2針對(duì)傳統(tǒng)方法通過(guò)人工設(shè)置KD-樹(shù)高度控制拉普拉斯噪音的缺陷，所設(shè)計(jì)的分割方法應(yīng)盡量避免所添加噪音對(duì)樹(shù)高度的依賴(lài)。

針對(duì)原則1，本文利用伯努利隨機(jī)抽樣技術(shù)抽樣空間數(shù)據(jù)點(diǎn)，并且該抽樣方法滿(mǎn)足差分隱私?；谠瓌t1，本文設(shè)計(jì)一種直接方法SKD-Tree。然而，SKD-Tree方法在添加拉普拉斯噪音時(shí)，沒(méi)有脫離對(duì)KD-樹(shù)高度的依賴(lài)。

針對(duì)原則2，本文利用滿(mǎn)足差分隱私的稀疏向量技術(shù)判斷KD-樹(shù)結(jié)點(diǎn)是否繼續(xù)分割。在分割結(jié)點(diǎn)時(shí)，判斷條件不再依賴(lài)樹(shù)的高度。基于原則1與原則2，本文設(shè)計(jì)一種高效方法KD-TSS來(lái)分割空間數(shù)據(jù)。

4.2 SKD-Tree算法實(shí)現(xiàn)

本節(jié)描述SKD-Tree算法的具體實(shí)現(xiàn)細(xì)節(jié)。

算法1 SKD-Tree算法

輸入：D，隱私預(yù)算ε，分割閾值θ，樹(shù)高度h。

輸出：滿(mǎn)足差分隱私的KD-樹(shù)T。

該算法包括兩個(gè)主要步驟：伯努利隨機(jī)抽樣（第1～2行）與KD-樹(shù)分割（第4～11行）。在利用KD-樹(shù)分割每個(gè)結(jié)點(diǎn)時(shí)，兩種操作至關(guān)重要：判斷每個(gè)結(jié)點(diǎn)中的噪音計(jì)數(shù)是否大于給定閾值θ（第7～8行）。對(duì)于可分割結(jié)點(diǎn)，利用指數(shù)機(jī)制選擇其分割中位線(xiàn)（第9行）。接下來(lái)介紹如何利用指數(shù)機(jī)制選擇中位線(xiàn)。

4.2.1 中位線(xiàn)選擇方法EM

因?yàn)樵跇?shù)結(jié)點(diǎn)中選擇中位數(shù)的過(guò)程，位于中位線(xiàn)上數(shù)據(jù)點(diǎn)的隱私有可能被泄露，所以該選擇過(guò)程需滿(mǎn)足差分隱私。本文利用指數(shù)機(jī)制實(shí)現(xiàn)該步驟。

設(shè)結(jié)點(diǎn)vi=＜x1,x2,…,xl＞的數(shù)據(jù)點(diǎn)屬于區(qū)間[a,b]，且x1≤x2≤…≤xl是按照升序排列。設(shè)xm是vi的真實(shí)中位數(shù)，任意取一個(gè)數(shù)值xi(xi∈[a,b])，則xi被選擇的概率如式（6）所示：

其中，rank(xi)表示xi在結(jié)點(diǎn)vi中的排名；Δrank表示排名函數(shù)的敏感性。在D中添加一個(gè)或者去掉一個(gè)數(shù)據(jù)點(diǎn)，rank函數(shù)的最大變化為1，因此Δrank=1。由式（6）可知，與真實(shí)中位數(shù)xm排名越接近的值，被選中的概率越大。

結(jié)合式（4）與式（6），算法SKD-Tree的第9行可表示為：

根據(jù)定理2可知，EM(vi,ε2)過(guò)程滿(mǎn)足ε2-差分隱私，進(jìn)而使得選擇中位數(shù)的過(guò)程不會(huì)泄露該值的隱私。

4.2.2 伯努利隨機(jī)抽樣過(guò)程

SKD-Tree算法的另外一個(gè)重要步驟是伯努利隨機(jī)抽樣，該過(guò)程的操作細(xì)節(jié)如下：首先確定抽樣概率γ，然后以γ對(duì)D做伯努利實(shí)驗(yàn)，如果實(shí)驗(yàn)成功，則獲得空間樣本，否則放棄該樣本。最后，計(jì)算出整個(gè)空間分割所需的隱私代價(jià)εγ（SKD-Tree算法第2行所示）。該過(guò)程的關(guān)鍵在于如何使得抽樣過(guò)程滿(mǎn)足差分隱私。文獻(xiàn)[15]給出的定理3說(shuō)明該過(guò)程滿(mǎn)足ln(1+γ(eε-1))-差分隱私。

定理3給定一個(gè)數(shù)據(jù)D，令方法A在D上滿(mǎn)足ε-差分隱私。如果方法Aγ操作包括：以概率γ從D中抽取樣本獲得，然后A作用于，則Aγ滿(mǎn)足ln(1+γ(eε-1))-差分隱私。

接下來(lái)要證明SKD-Tree算法如何滿(mǎn)足ε-差分隱私。如定理4所示。

定理4 SKD-Tree算法滿(mǎn)足ε-差分隱私。

證明 設(shè)A是SKD-Tree沒(méi)有抽樣操作的算法，即是算法SKD-Tree去掉第1行與第2行。Aγ表示SKD-Tree算法本身。首先證明A滿(mǎn)足εγ-差分隱私。

算法A中只有第7行與第9行用到隱私代價(jià)。第7行為每個(gè)結(jié)點(diǎn)添加Lap(h/ε1)大小的噪音，其原因是在D中添加或去掉一個(gè)數(shù)據(jù)點(diǎn)時(shí)，最多影響h個(gè)結(jié)點(diǎn)的計(jì)數(shù)。結(jié)合差分隱私并行性質(zhì)[16]與順序性質(zhì)[16]，利用定理1可知，第7行滿(mǎn)足ε1-差分隱私。結(jié)合定理2可知，第9行滿(mǎn)足ε2-差分隱私。由于第7行與第9行是順序執(zhí)行，并且εγ=ε1+ε2，因此A滿(mǎn)足εγ-差分隱私。

由于εγ=ln(eε-1+γ)-lnγ，結(jié)合定理3可知，算法Aγ滿(mǎn) 足差分隱私。把εγ帶入，則ln(1+γ(eln(eε-1+γ)-lnγ-1))=ε，因此可知算法Aγ滿(mǎn)足ε-差分隱私，由于Aγ表示SKD-Tree算法本身，則SKD-Tree滿(mǎn)足ε-差分隱私。

由上述的分析可知，SKD-Tree算法只是利用抽樣技術(shù)克服了海量數(shù)據(jù)帶來(lái)的分割困難。由式（5）可知，SKD-Tree算法的查詢(xún)誤差由樹(shù)高度h控制。然而，啟發(fā)式設(shè)定h非常困難，h過(guò)大或者過(guò)小均會(huì)造成范圍查詢(xún)的精度較低。為了同時(shí)滿(mǎn)足原則1與原則2，本文設(shè)計(jì)一種更有效的算法KD-TSS。

4.3 KD-TSS算法實(shí)現(xiàn)

本節(jié)描述KD-TSS算法的具體實(shí)現(xiàn)細(xì)節(jié)。

算法2 KD-TSS算法

輸入：D，隱私預(yù)算ε，分割閾值θ。

輸出：滿(mǎn)足差分隱私的KD-樹(shù)T。

該算法的核心步驟包括稀疏向量技術(shù)SVT（第4～6行）與KD-樹(shù)的重構(gòu)技術(shù)Re-Gen-Tree（第10行）。利用SVT判斷結(jié)點(diǎn)是否被分割（第6～8行），若滿(mǎn)足條件，則利用EM函數(shù)分割該結(jié)點(diǎn)。結(jié)合所有的葉子結(jié)點(diǎn)噪音計(jì)數(shù)，利用Re-Gen-Tree重新構(gòu)造KD-樹(shù)。利用重構(gòu)的KD-樹(shù)來(lái)響應(yīng)范圍計(jì)數(shù)查詢(xún)。在為結(jié)點(diǎn)添加噪音時(shí)，不再依賴(lài)于樹(shù)高度h，其原因是KD-TSS算法并不實(shí)際保存中間結(jié)點(diǎn)的噪音計(jì)數(shù)。中間結(jié)點(diǎn)的噪音計(jì)數(shù)只是與SVT計(jì)算出的閾值進(jìn)行比較，相當(dāng)于一個(gè)“是/否”的應(yīng)答。接下來(lái)介紹稀疏向量技術(shù)。

4.3.1 稀疏向量技術(shù)

稀疏向量技術(shù)（SVT）[17-19]通常用來(lái)響應(yīng)有限個(gè)大于某閾值的計(jì)數(shù)查詢(xún)。該技術(shù)包含兩個(gè)主要步驟：一是尋找合適的閾值θ，添加噪音后獲得二是對(duì)每個(gè)查詢(xún)結(jié)果c(v)添加噪音后獲得，并與噪音閾值比較。比較結(jié)果有兩種：一是若則輸出；否則輸出一個(gè)標(biāo)識(shí)符號(hào)⊥。本文SVT技術(shù)的具體表示形式如式（8）所示：

不同于文獻(xiàn)[5]，本文在計(jì)算結(jié)點(diǎn)噪音值的過(guò)程中并不分割隱私代價(jià)ε1，其原因是在利用SVT分割結(jié)點(diǎn)時(shí)，被分割結(jié)點(diǎn)中的噪音值并沒(méi)有實(shí)際保存到該結(jié)點(diǎn)中，與僅在形式上進(jìn)行比較。例如，設(shè)定圖2中的KD-樹(shù)扇出為4，對(duì)v4結(jié)點(diǎn)進(jìn)行判斷是否繼續(xù)分割。由于則v4結(jié)點(diǎn)被分割成4個(gè)結(jié)點(diǎn)。然而值6+Lap(2/ε1)卻沒(méi)有保存在v4結(jié)點(diǎn)中。由于v2、v3、v5結(jié)點(diǎn)中的噪音值小于則不再繼續(xù)分割。對(duì)于v2、v3、v5這樣的結(jié)點(diǎn)，具體的噪音值應(yīng)保存在結(jié)點(diǎn)中（算法2中的第4行）。例如v2結(jié)點(diǎn)中的噪音計(jì)數(shù)為1+Lap(2/ε1)。

接下來(lái)一個(gè)關(guān)鍵問(wèn)題是如何找到合適的閾值θ。為了找到恰當(dāng)?shù)摩?，首先不考慮數(shù)據(jù)點(diǎn)隱私，結(jié)合空間數(shù)據(jù)點(diǎn)構(gòu)建KD-樹(shù)。然后記錄所有葉子結(jié)點(diǎn)中的計(jì)數(shù)值{c(v1),c(v2),…,c(vi)}，求出{c(v1),c(v2),…,c(vi)}的中值作為閾值θ。

當(dāng)利用SVT對(duì)空間分割后，形成了相應(yīng)的KD-樹(shù)結(jié)構(gòu)。樹(shù)中所有的葉子結(jié)點(diǎn)記錄相應(yīng)的噪音值。由于在分割過(guò)程中，一些結(jié)點(diǎn)的噪音值沒(méi)有被保存下來(lái)，如何恢復(fù)這些結(jié)點(diǎn)的噪音值是另一個(gè)關(guān)鍵問(wèn)題。接下來(lái)介紹如何利用葉子結(jié)點(diǎn)計(jì)數(shù)值重構(gòu)KD-樹(shù)。

4.3.2 KD-樹(shù)重構(gòu)過(guò)程Re-Gen-Tree

滿(mǎn)足差分隱私的KD-樹(shù)空間分割，其最終目的是能夠精確響應(yīng)范圍查詢(xún)。給定一個(gè)范圍查詢(xún)Q，在遍歷樹(shù)過(guò)程中，Q與樹(shù)中結(jié)點(diǎn)v交集存在幾種情況：（1）Q完全包含v，此時(shí)v中的數(shù)據(jù)點(diǎn)全部落入Q中；（2）Q與v沒(méi)有交集，此時(shí)拋棄結(jié)點(diǎn)v；（3）Q與v部分相交，此時(shí)利用相交部分響應(yīng)Q。

在利用SVT與EM對(duì)結(jié)點(diǎn)進(jìn)行分割時(shí)，一些結(jié)點(diǎn)的噪音值并沒(méi)有被記錄下來(lái)。如果只利用最終的葉子結(jié)點(diǎn)響應(yīng)范圍計(jì)數(shù)查詢(xún)，查詢(xún)精度與查詢(xún)效率會(huì)非常低。例如，圖2中給出范圍查詢(xún)Q，自頂向下遍歷KD-樹(shù)，得到響應(yīng)結(jié)點(diǎn)v1、v4、v5、v9。然而，由于結(jié)點(diǎn)v4中的噪音值沒(méi)有被記錄，無(wú)法精確響應(yīng)Q。

Fig.2 An example of KD-Tree decomposition圖2 KD-樹(shù)分割實(shí)例

為了能夠比較精確地響應(yīng)范圍查詢(xún)，本文設(shè)計(jì)了KD-樹(shù)重構(gòu)算法。

算法3 Re-Gen-Tree

輸入：僅有葉子結(jié)點(diǎn)計(jì)數(shù)的KD-樹(shù)T。

輸出：各結(jié)點(diǎn)均有計(jì)數(shù)的樹(shù)T。

算法Re-Gen-Tree主要包含兩個(gè)過(guò)程top-downtravel(T)與bottom-up-travel(T,S)。其中top-down-travel(T)主要用來(lái)尋找那些被分割的結(jié)點(diǎn)，并存入S中（過(guò)程1的第7行），同時(shí)把葉子結(jié)點(diǎn)的噪音計(jì)數(shù)疊加到其父結(jié)點(diǎn)中（過(guò)程1的第4～5行）。bottom-up-travel(T,S)過(guò)程主要用來(lái)恢復(fù)那些被分割卻沒(méi)有噪音計(jì)數(shù)的結(jié)點(diǎn)（過(guò)程2的第2～5行）。

例如，圖2結(jié)點(diǎn)中紅色數(shù)字為噪音值，黑色數(shù)字為真實(shí)計(jì)數(shù)值。自頂向下遍歷KD-樹(shù)，結(jié)點(diǎn)v1與結(jié)點(diǎn)v4中沒(méi)有實(shí)際的計(jì)數(shù)值。把結(jié)點(diǎn)v1與結(jié)點(diǎn)v4放入S中，把疊加到結(jié)點(diǎn)v1中，把疊加到結(jié)點(diǎn)v4中，得到。然后，自底向上遍歷KD-樹(shù)，疊加到結(jié)點(diǎn)v1中，得到。得到所有結(jié)點(diǎn)的噪音值后，即可應(yīng)用重構(gòu)后的KD-樹(shù)響應(yīng)范圍查詢(xún)。

接下來(lái)比較KD-TSS與SKD-Tree的范圍查詢(xún)誤差。根據(jù)式（5），設(shè)ErrorKD-TSS(Q)表示KD-TSS的查詢(xún)誤差，ErrorSKD-Tree(Q)表示SKD-Tree的查詢(xún)誤差。

定理5在大規(guī)模空間數(shù)據(jù)環(huán)境中，KD-TSS與SKD-Tree的查詢(xún)誤差滿(mǎn)足不等式ErrorKD-TSS(Q)＜ErrorSKD-Tree(Q)。

證明 利用反證法進(jìn)行證明。

假設(shè)ErrorKD-TSS(Q)＞ErrorSKD-Tree(Q)。根據(jù)式（5）可知，ErrorSKD-Tree(Q)=q(1-γ)/γ+2q(h/ε)2，ErrorKD-TSS(Q)=q(1-γ)/γ+2q(2/ε1)2。假設(shè) KD-TSS與SKD-Tree采用相同的抽樣概率，落入Q查詢(xún)中的數(shù)據(jù)點(diǎn)相同，則不等式ErrorKD-TSS(Q)＞ErrorSKD-Tree(Q)，使得如下不等式(2/ε1)2＞(h/ε)2成立。進(jìn)而使得h＜2ε/ε1成立。由于ε1為KD-樹(shù)中的葉子結(jié)點(diǎn)添加噪音，通常ε/ε1≤ 2，進(jìn)而得到h≤4。由于KD-樹(shù)通常表示成二叉樹(shù)，則。而在數(shù)據(jù)點(diǎn)達(dá)到百萬(wàn)級(jí)別，h≤4不成立。因此，不等式ErrorKD-TSS(Q)＜ErrorSKD-Tree(Q)成立。

4.4 KD-TSS算法隱私性分析

KD-TSS算法的隱私性主要從ε-差分隱私的概念和性質(zhì)的角度來(lái)證明，論證KD-TSS算法是否滿(mǎn)足ε-差分隱私。

定理6 KD-TSS算法滿(mǎn)足ε-差分隱私。

證明 根據(jù)算法2可知，用到隱私代價(jià)的只有SVT技術(shù)（KD-TSS中第4～6行）與EM操作（KD-TSS中第7行）。根據(jù)定理2可知，EM操作滿(mǎn)足ε2-差分隱私。因此，只要證明SVT技術(shù)滿(mǎn)足ε1-差分隱私，即可推理出KD-TSS滿(mǎn)足ε-差分隱私。

在利用SVT技術(shù)判斷KD-樹(shù)的結(jié)點(diǎn)是否被分割時(shí)，相當(dāng)于系列的“是/否”應(yīng)答。因此，為了證明方便，采用二元向量v=＜x1,x2,…,xt＞記錄結(jié)點(diǎn)是否分割。如果則xi=1，表示結(jié)點(diǎn)vi被分割；否則，xi=0，表示vi沒(méi)被分割。此時(shí)vi為葉子結(jié)點(diǎn)。

給定兩個(gè)近鄰空間數(shù)據(jù)集D與D′，Pr1(v)與Pr2(v)分別表示SVT作用于D與D′輸出v的概率。設(shè)x＜i表示向量v中前i-1個(gè)響應(yīng)記錄。由條件概率定理可知：

由式(9)可知，當(dāng)x＜i固定后，使得xi=1，使得xi=0。因此，與的分布僅僅是拉普拉斯分布。

假設(shè)x是D上某個(gè)分割閾值，設(shè)Hi(x)表示D上x(chóng)i=1的概率，H′i(x)表示D′上x(chóng)i=1的概率。因此，Hi(x)可以描述如下表達(dá)式：

其中，Lap(λ)表示拉普拉斯分布產(chǎn)生的獨(dú)立噪音。

根據(jù)全局敏感性定義可知，計(jì)數(shù)c(v)的敏感性為1，即?=1。設(shè)c(vi)與c′(vi)分別表示D與D′上結(jié)點(diǎn)vi的計(jì)數(shù)，c′(vi)=c(vi)+1，進(jìn)而得μ=y+1。重寫(xiě)Hi(x)，則Hi(x)可以表達(dá)成如下公式：

同理，可以獲得如下不等式：

把式（10）與式（11）帶入式（9）可知：

由定義1可知，SVT技術(shù)滿(mǎn)足ε1-差分隱私。

由于εγ=ε1+ε2，并且εγ=ln(eε-1+γ)-lnγ，進(jìn)而可以推理出。因此，KDTSS算法滿(mǎn)足ε-差分隱私。

5 實(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)采用兩個(gè)數(shù)據(jù)集NYC（http://publish.illinois.edu/dbwork/open-data）與 Beijing（http://research.microsoft.com/apps/pubs/?id=152883），其中NYC數(shù)據(jù)集是整個(gè)2011年12個(gè)月內(nèi)紐約市出租車(chē)的乘車(chē)和下車(chē)地理坐標(biāo)數(shù)據(jù)，該數(shù)據(jù)集包含1 000萬(wàn)條信息；Beijing數(shù)據(jù)集是2011年北京市二月份某一周內(nèi)10 357輛出租車(chē)的乘車(chē)和下車(chē)地理坐標(biāo)數(shù)據(jù)，該數(shù)據(jù)集包含1 500萬(wàn)條信息。兩種數(shù)據(jù)集具體細(xì)節(jié)與可視化結(jié)果分別如表1與圖3、圖4所示。

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

Fig.3 Visualization of NYC dataset圖3 NYC數(shù)據(jù)集可視化結(jié)果

Fig.4 Visualization of Beijing dataset圖4 Beijing數(shù)據(jù)集可視化結(jié)果

結(jié)合上述兩種數(shù)據(jù)集，采用相對(duì)誤差（relative error，RE）度量 SKD-Tree、KD-TSS、KD-Stand 以及KD-Hybrid算法的可用性。相對(duì)誤差如式（12）所示：

其中，Q(D)表示D上真實(shí)的范圍查詢(xún)結(jié)果；表示D上范圍查詢(xún)的噪音結(jié)果；Δ為平滑因子，其值為實(shí)驗(yàn)數(shù)據(jù)集大小的0.1%。

本文設(shè)置伯努利隨機(jī)抽樣概率為1%，隱私預(yù)算參數(shù)ε的取值為0.1、0.5、1.0。實(shí)驗(yàn)中范圍查詢(xún)Q的查詢(xún)范圍分別覆蓋NYC與Beijing兩種數(shù)據(jù)集的[1%,1%]、[5%,5%]、[10%,10%]，在每種查詢(xún)范圍內(nèi)隨機(jī)生成5 000次查詢(xún)。

（1）基于NYC數(shù)據(jù)集的KD-TSS、SKD-Tree、KDStand以及KD-Hybrid算法RE值比較

通過(guò)改變隱私預(yù)算參數(shù)ε值來(lái)對(duì)比KD-TSS、SKD-Tree、KD-Stand以及KD-Hybrid算法響應(yīng)固定范圍查詢(xún)的相對(duì)誤差，進(jìn)而對(duì)比4種算法的可用性。

圖5表示NYC數(shù)據(jù)集范圍查詢(xún)結(jié)果。由圖5（a）～（c）可以發(fā)現(xiàn)，當(dāng)查詢(xún)范圍固定到[1%,1%]、[5%,5%]、[10%,10%]時(shí)，ε從0.1變化到1.0，KD-TSS算法所取得的查詢(xún)精度是SKD-Tree算法的將近3倍，是KDStand與KD-Hybrid算法的將近10倍。特別是查詢(xún)范圍為[1%,1%]時(shí)，將近13倍。圖5（d）～（f）顯示，當(dāng)查詢(xún)范圍從[1%,1%]變化到[10%,10%]，ε分別固定為0.1、0.5、1.0時(shí)，KD-TSS算法取得的范圍查詢(xún)精度是SKD-Tree算法的將近2倍，是KD-Stand與KD-Hybrid算法的將近12倍。此外，從圖5（a）～（f）可以看出，SKD-Tree算法同樣優(yōu)于KD-Stand與KD-Hybrid算法。其主要原因是NYC數(shù)據(jù)偏斜比較嚴(yán)重，而KD-TSS與SKD-Tree算法通過(guò)抽樣技術(shù)能較好地避免偏斜問(wèn)題。同時(shí)KD-TSS采用SVT技術(shù)避免了對(duì)隱私代價(jià)的多層次分割。

（2）基于 Beijing數(shù)據(jù)集的 KD-TSS、SKD-Tree、KD-Stand以及KD-Hybrid算法RE值比較

由圖6（a）～（c）可以看出，變化ε時(shí)，KD-TSS算法所取得的查詢(xún)精度稍微好于SKD-Tree算法，是KDStand與KD-Hybrid算法的3倍多。圖6（e）～（f）顯示，查詢(xún)范圍從[5%,5%]變化到[10%,10%]，ε固定時(shí)，KD-TSS算法取得的范圍查詢(xún)精度是SKD-Tree算法的將近2倍。查詢(xún)范圍從[1%,1%]變化到[10%,10%]時(shí)，KD-TSS算法取得的查詢(xún)精度是KD-Stand與KDHybrid算法的將近4倍。其原因是Beijing數(shù)據(jù)的偏斜度不是很大（參考圖4），由于KD-TSS算法同時(shí)采用了抽樣與SVT技術(shù)，其查詢(xún)精度優(yōu)于同類(lèi)算法。

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

針對(duì)差分隱私保護(hù)下基于KD-樹(shù)空間數(shù)據(jù)分割存在的問(wèn)題，本文首先對(duì)現(xiàn)有方法進(jìn)行分析，并在此基礎(chǔ)上提出了基于伯努利隨機(jī)抽樣技術(shù)的算法SKDTree。由于SKD-Tree依賴(lài)KD-樹(shù)高度添加拉普拉斯噪音，重新提出了另外一種基于抽樣與稀疏向量技術(shù)的算法KD-TSS。從理論角度進(jìn)行分析的結(jié)果顯示，SKD-Tree與KD-TSS算法分別滿(mǎn)足差分隱私。最后，在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明SKD-Tree與KD-TSS算法能夠輸出比較精確的范圍查詢(xún)結(jié)果。未來(lái)工作考慮高維度空間數(shù)據(jù)的分割問(wèn)題。

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

[1]Sweeney L.K-anonymity:a model for protecting privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570.

[2]Dwork C,McSherry F,Nissim K,et al.Calibrating noise to sensitivity in private data analysis[C]//LNCS 3876:Proceedings of the 3rd Theory of Cryptography Conference,New York,Mar 4-7,2006.Berlin,Heidelberg:Springer,2006:265-284.

[3]Dwork C.Differential privacy[C]//LNCS 4052:Proceedings of the 33rd International Colloquium on Automata,Languages and Programming,Venice,Italy,Jul 10-14,2006.Berlin,Heidelberg:Springer,2006:1-12.

[4]Dwork C,Lei J.Differential privacy and robust statistics[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing,Bethesda,USA,May 31-Jun 2,2009.New York:ACM,2009:371-380.

[5]de Montjoye Y A,Hidalgo C A,Verleysen M,et al.Unique in the crowd:the privacy bounds of human mobility[J].Scientific Reports,2013,3(6):1376.

[6]Xiao Yonghui,Xiong Li,Yuan Chun.Differentially private data release through multidimensional partitioning[C]//LNCS 6358:Proceedings of the 7th VLDB Workshop on Secure Data Management,Singapore,Sep 17,2010.Berlin,Heidelberg:Springer,2010:150-168.

[7]Cormode G,Procopiuc C,Srivastava D,et al.Differentially private spatial decompositions[C]//Proceedings of the 28th International Conference on Data Engineering,Washington,Apr 1-5,2012.Washington:IEEE Computer Society,2012:20-31.

[8]McSherry F,Talwar K.Mechanism design via differential privacy[C]//Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science,Providence,USA,Oct 21-23,2007.Washington:IEEE Computer Society,2007:94-103.

[9]Xu Jia,Zhang Zhenjie,Xiao Xiaokui,et al.Differential private histogram publication[J].International Journal of Very Large Database,2013,22(6):797-822.

[10]Zhang Jun,Cormode G,Procopiuc C M,et al.PrivBayes:private data release via Bayesian networks[C]//Proceedings of the 2014 International Conference on Management of Data,Snowbird,USA,Jun 22-27,2014.New York:ACM,2014:1423-1434.

[11]Su Sen,Tang Peng,Cheng Xiang,et al.Differentially private multi-party high-dimensional data publishing[C]//Proceedings of the 32nd International Conference on Data Engineering,Helsinki,Finland,May 16-20,2016.Washington:IEEE Computer Society,2016:205-216.

[12]Zhang Jun,Xiao Xiaokui,Xie Xing.PrivTree:a differentially private algorithm for hierarchical decompositions[C]//Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data,San Francisco,USA,Jun 26-Jul 1,2016.New York:ACM,2016:155-170.

[13]Qardaji W H,Yang Weining,Li Ninghui.Differentially private grids for geospatial data[C]//Proceedings of the 29th International Conference on Data Engineering,Brisbane,Australia,Apr 8-12,2013.Washington:IEEE Computer Society,2013:757-768.

[14]Chen Rui,Shen Yilin,Jin Hongxia.Private analysis of infinite data streams via retroactive grouping[C]//Proceedings of the 24th International Conference on Information and Knowledge Management,Melbourne,Australia,Oct 19-23,2015.New York:ACM,2015:1061-1070.

[15]Li Ninghui,Qardaji W H,Su Dong.On sampling,anonymization,and differential privacy or,k-anonymization meets differential privacy[C]//Proceedings of the 7th ACM Symposium on Information,Computer and Communications Security,Seoul,May 2-4,2012.New York:ACM,2012:32-33.

[16]McSherry F.Privacy integrated queries:an extensible platform for privacy-preserving data analysis[C]//Proceedings of the 2009 International Conference on Management of Data,Providence,USA,Jun 29-Jul 2,2009.New York:ACM,2009:19-30.

[17]Hardt M A W.A study of privacy and fairness in sensitive data analysis[D].Princeton:Princeton University,2011.

[18]Lee J,Clifton C W.Top-kfrequent itemsets via differentially private FP-trees[C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,Aug 24-27,2014.New York:ACM,2014:931-940.

[19]Chen Rui,Xiao Qiao,Zhang Yu,et al.Differentially private high-dimensional data publication via sampling-based inference[C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Sydney,Australia,Aug 10-13,2015.New York:ACM,2015:129-138.

KD-TSS:Accurate Method for Private Spatial Decomposition*

JIN Kaizhong1,ZHANG Xiaojian1+,PENG Huili1,2
1.College of Computer and Information Engineering,Henan University of Economics and Law,Zhengzhou 450046,China
2.Henan Radio&Television University,Zhengzhou 450008,China

A

TP392

+Corresponding author:E-mail:xjzhagn82@ruc.edu.cn

JIN Kaizhong,ZHANG Xiaojian,PENG Huili.KD-TSS:accurate method for private spatial decomposition.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1579-1590.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1579-12

10.3778/j.issn.1673-9418.1608040

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Natural Science Foundation of China under Grant No.61502146(國(guó)家自然科學(xué)基金);the Key Technologies Research and Development Program of Henan Province under Grant No.162102310411(河南省科技攻關(guān)項(xiàng)目);the Research Program of Higher Education of Henan Educational Committee under Grant No.16A520002(河南省教育廳高等學(xué)校重點(diǎn)科研項(xiàng)目);the Youth Backbone Teacher Program of Higher Education of Henan Province under Grant No.2013GGJS-098(河南省高等學(xué)校青年骨干教師項(xiàng)目);the Young Talents Fund of Henan University of Economics and Law(河南財(cái)經(jīng)政法大學(xué)青年拔尖人才資助計(jì)劃);the Technology Bureau Project of Zhengzhou under Grant No.153PKJGG115(鄭州市科技局普通科技攻關(guān)項(xiàng)目).

Received 2016-08,Accepted 2016-11.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-11-29,http://www.cnki.net/kcms/detail/11.5602.TP.20161129.1454.002.html

JIN Kaizhong was born in 1991.He is an M.S.candidate at College of Computer and Information Engineering,Henan University of Economics and Law,and the student member of CCF.His research interests include differential privacy and database,etc.

金凱忠（1991—），男，河南開(kāi)封人，河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院碩士研究生，CCF學(xué)生會(huì)員，主要研究領(lǐng)域?yàn)椴罘蛛[私，數(shù)據(jù)庫(kù)等。

ZHANG Xiaojian was born in 1980.He received the Ph.D.degree from School of Information,Renmin University of China in 2014.Now he is an associate professor at Henan University of Economics and Law,and the member of CCF.His research interests include differential privacy and database,etc.

張嘯劍（1980—），男，河南周口人，2014年于中國(guó)人民大學(xué)信息學(xué)院獲得博士學(xué)位，現(xiàn)為河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)椴罘蛛[私，數(shù)據(jù)庫(kù)等。

PENG Huili was born in 1981.She received the M.S.degree from School of Information,Yanshan University in 2007.Now she is a lecturer at Henan Radio&Television University.Her research interests include database and privacy protection,etc.

彭慧麗（1981—），女，河南周口人，2007年于燕山大學(xué)信息學(xué)院獲得碩士學(xué)位，現(xiàn)為河南廣播電視大學(xué)講師，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)，隱私保護(hù)等。