差分隱私的查詢一致性約束研究*

賈俊杰，陳 慧，馬慧芳，牟玉祥

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

1 引言

隨著互聯(lián)網(wǎng)大數(shù)據(jù)時代的到來，網(wǎng)絡(luò)上每時每刻都在產(chǎn)生大量的數(shù)據(jù)記錄，如購物記錄、Web點(diǎn)擊流等事務(wù)信息。這些數(shù)據(jù)發(fā)布后由企業(yè)和機(jī)構(gòu)所收集和共享，通過挖掘其中的知識，為用戶提供更精準(zhǔn)的服務(wù)。但是，數(shù)據(jù)發(fā)布在為企業(yè)決策和科學(xué)研究工作提供巨大便利的同時，也給數(shù)據(jù)個體帶來隱私泄露的威脅。隱私保護(hù)的數(shù)據(jù)發(fā)布技術(shù)作為當(dāng)前數(shù)據(jù)安全領(lǐng)域的研究熱點(diǎn)，在為數(shù)據(jù)分析提供足夠多信息的同時也保護(hù)數(shù)據(jù)個體的隱私安全。目前隱私保護(hù)技術(shù)主要分為2類[1]：第1類是基于分組的隱私保護(hù)模型，如k-匿名[2]、l-多樣性[3]、t-相近[4]等，這類模型都需要特定的攻擊假設(shè)和背景知識；第2類是Dwork[5]在2006年針對統(tǒng)計(jì)數(shù)據(jù)提出的差分隱私保護(hù)模型，該模型不存在任何攻擊，通過向真實(shí)答案中添加噪聲干擾以達(dá)到對數(shù)據(jù)個體的隱私保護(hù)。

統(tǒng)計(jì)數(shù)據(jù)的發(fā)布主要使用直方圖形式，因直方圖直觀的數(shù)據(jù)分布形式，其結(jié)果可作為統(tǒng)計(jì)查詢的直接依據(jù)[6]。生成直方圖時，需根據(jù)不相交的查詢區(qū)間將數(shù)據(jù)劃分為不同的區(qū)間，再分別統(tǒng)計(jì)每個區(qū)間的計(jì)數(shù)值，為提供差分隱私的保護(hù)，最常用的方法是向每個區(qū)間分別添加獨(dú)立的符合Laplace分布的噪聲值。這些查詢區(qū)間為不相交的子集，所以區(qū)間查詢的敏感度為1，這樣的差分隱私直方圖發(fā)布保證了數(shù)據(jù)個體的隱私。但是，對于通用直方圖(即查詢區(qū)間子集相交的直方圖)[7]，每個區(qū)間是不規(guī)則的且與其他區(qū)間有重疊部分，若向通用直方圖的區(qū)間直接添加Laplace噪聲，可能會出現(xiàn)范圍查詢的不一致性問題。例如，1組查詢序列的結(jié)果為A={a1,a2,a3}，存在a1=a2+a3的約束關(guān)系，向A中添加Laplace噪聲之后得到的結(jié)果：a′1≠a2+a3，違背了原始的約束關(guān)系。

因此，本文針對查詢不一致的問題提出一致性調(diào)整算法，先將1組子集相交的區(qū)間查詢映射到1棵滿k-叉區(qū)間樹上，其中同一層節(jié)點(diǎn)上的區(qū)間值不相交，再向樹中每個節(jié)點(diǎn)添加符合Laplace分布的隨機(jī)噪聲，得到1棵差分隱私滿k-叉區(qū)間樹。將樹進(jìn)行一致性調(diào)整后生成滿足一致性約束的滿k-叉區(qū)間樹，遍歷后得到1組調(diào)整后的序列，實(shí)現(xiàn)差分隱私的一致性約束。實(shí)驗(yàn)結(jié)果表明，經(jīng)過調(diào)整后的數(shù)據(jù)滿足一致性約束且比直接添加噪聲后的數(shù)據(jù)更接近真實(shí)值，實(shí)現(xiàn)了隱私保護(hù)目的，且時間運(yùn)行效率優(yōu)于LBLUE算法的。

2 相關(guān)工作介紹

Dwork[5]提出的差分隱私模型不存在任何的隱私攻擊，且該模型具有強(qiáng)大的數(shù)學(xué)背景知識，致使差分隱私迅速成為了隱私保護(hù)研究領(lǐng)域的熱點(diǎn)。直方圖發(fā)布作為一種直觀的數(shù)據(jù)分析方法，將利用差分隱私保護(hù)后的數(shù)據(jù)以直方圖的形式發(fā)布，更利于數(shù)據(jù)研究者分析，因此目前已有大量的文獻(xiàn)提出基于差分隱私保護(hù)的直方圖發(fā)布算法。2006年，Dwork等人[8]最早提出基于差分隱私模型的直方圖發(fā)布，通過向直方圖中的每個區(qū)間直接添加噪聲來達(dá)到隱私保護(hù)的目的。2011年，Xiao等人[9]提出通過小波變換技術(shù)實(shí)現(xiàn)差分隱私保護(hù)的直方圖發(fā)布方法Privelet，利用小波變換將直方圖數(shù)據(jù)轉(zhuǎn)換為小波樹，再向樹中添加噪聲實(shí)現(xiàn)差分隱私，逆轉(zhuǎn)換小波樹得到需發(fā)布的直方圖數(shù)據(jù)。2012年，Acs等人[10]利用貪心策略將近鄰的查詢區(qū)間聚類成1個簇，再根據(jù)每個簇的大小不同添加噪聲。在直方圖中直接添加噪聲后進(jìn)行查詢，會因區(qū)間值內(nèi)噪聲值疊加導(dǎo)致偏差過大的問題。2013年，Xu等人[11]提出StructureFirst算法，利用指數(shù)機(jī)制確定不同分組間的界限，再向不同組添加噪聲。2016年，張嘯劍等人[12]提出基于差分隱私的直方圖發(fā)布方法DiffHR，利用Metropolis-Hastings技術(shù)與指數(shù)機(jī)制對直方圖數(shù)據(jù)進(jìn)行排序，排序后使用一種貪心聚類方法提高精確度。2019年，張宇軒等人[13]利用度排序的邊移除方法給出了2種點(diǎn)差分隱私下圖的度分布直方圖發(fā)布機(jī)制，這2種發(fā)布機(jī)制在達(dá)到隱私保護(hù)的前提下，還提高了數(shù)據(jù)的可用性。

目前關(guān)于差分隱私直方圖的發(fā)布主要針對精確度的問題做研究，針對不一致現(xiàn)象的研究較少，Hay等人[7]首次提出針對差分隱私直方圖發(fā)布的不一致問題，使用約束推理的后處理方法，解決查詢存在的不一致現(xiàn)象，結(jié)果證明經(jīng)過處理后的答案接近真實(shí)值且滿足一致性約束。Lee等人[14]為進(jìn)一步提高一致性約束后直方圖的精確度，將后處理步驟轉(zhuǎn)換為約束極大似然估計(jì)問題，提出一種基于交替方向乘子法ADMM(Alternating Direction Method of Multipliers)的通用方法，該方法適用于各種應(yīng)用。吳英杰等人[15]通過構(gòu)造局部的區(qū)間樹，實(shí)現(xiàn)局部最優(yōu)線性無偏估計(jì)，使用迭代次數(shù)以達(dá)到全局最優(yōu)線性無偏估計(jì)。因此，本文提出全局的一致性調(diào)整CA(Coherence Adjustment)算法，該算法既解決了不一致問題又保證了數(shù)據(jù)的精確度。

3 相關(guān)技術(shù)介紹

3.1 差分隱私

差分隱私模型使數(shù)據(jù)通過某種差分隱私隨機(jī)算法K發(fā)布并面向用戶提供查詢接口。算法K不依賴于特定的數(shù)據(jù)表，利用隨機(jī)噪聲對輸出數(shù)據(jù)進(jìn)行擾亂，數(shù)據(jù)表中的每1條記錄均得到了完全相同程度的保護(hù)，使得在統(tǒng)計(jì)意義上攻擊者無論具有何種背景知識，都無法識別任意1條記錄是否在原數(shù)據(jù)表中。

定義1(兄弟數(shù)據(jù)集) 2個數(shù)據(jù)集D和D′，有且僅有1條記錄不同，記為|DΔD′|=1，則稱D與D′為1對兄弟數(shù)據(jù)集。

定義2[5](ε-差分隱私) 對任意1對兄弟數(shù)據(jù)集D和D′，存在隨機(jī)算法F(D)和F(D′)滿足：

Pr(F(D)∈S)≤exp(ε)×Pr(F(D′)∈S)

(1)

則稱算法F滿足ε-差分隱私。其中S表示任意的輸出集合，ε表示隱私預(yù)算，隱私預(yù)算越大，隱私保護(hù)程度越低，數(shù)據(jù)可用性越高，通常情況下，ε取[0,1]的實(shí)數(shù)。

定義3[5](全局敏感度) 有1對兄弟數(shù)據(jù)集D和D′，對于任意函數(shù)f(D)∈R，則其全局敏感度Δf表示為：

Δf=max‖f(D)-f(D′)‖p

(2)

其中，R為函數(shù)所映射的實(shí)數(shù)空間，‖f(D)-f(D′)‖p表示數(shù)據(jù)集D與D′之間的Lp距離。

差分隱私保護(hù)主要通過向真實(shí)數(shù)據(jù)添加噪聲來實(shí)現(xiàn)，常見添加噪聲的機(jī)制包括Laplace機(jī)制和指數(shù)機(jī)制，其中Laplace機(jī)制主要針對數(shù)值型數(shù)據(jù)，指數(shù)機(jī)制通常用于需要對輸入數(shù)據(jù)進(jìn)行復(fù)雜操作的算法，例如針對離散型數(shù)據(jù)的分類操作。本文采用Laplace機(jī)制分析計(jì)數(shù)查詢的一致性約束問題。

定義4[5](Laplace機(jī)制) Laplace機(jī)制通過向查詢請求結(jié)果f(D)中添加隨機(jī)擾動噪聲η，得到輸出值f(D)+η實(shí)現(xiàn)ε-差分隱私保護(hù)，則Laplace分布的概率密度函數(shù)為：

(3)

由式(3)可得，Laplace噪聲滿足期望為0、方差為2λ2的Laplace(λ)分布。噪聲尺度參數(shù)λ值越大，所添加的噪聲幅度越高，隱私保護(hù)程度也越大。對于任意函數(shù)f(D)∈Rd，若算法F的輸出結(jié)果滿足：

(4)

則F滿足ε-差分隱私保護(hù)。其中d為區(qū)間查詢長度。由式(4)可得，添加的噪聲尺度參數(shù)λ=Δf/ε，λ大小與全局敏感度Δf成正比，與隱私預(yù)算ε成反比。

性質(zhì)1[5]設(shè)有算法F1,F2,…,Fn，隱私預(yù)算分別為ε1,ε2,…,εn，那么對于不相交的數(shù)據(jù)集D1,D2,…,Dn，由這些算法構(gòu)成的組合算法F(F1(D1),F2(D2),…,Fn(Dn))滿足(maxεi)-差分隱私保護(hù)，該性質(zhì)稱為“并行組合性”。

3.2 k-叉區(qū)間樹

統(tǒng)計(jì)直方圖的發(fā)布按數(shù)據(jù)表不同的屬性進(jìn)行劃分，形成1個或多個屬性不相交的集合，利用集合的計(jì)數(shù)值來直觀地表示數(shù)據(jù)的分布信息。

定義5(計(jì)數(shù)查詢) 設(shè)有n條記錄的數(shù)據(jù)表T，其中包含屬性x，用戶通過查詢Q訪問數(shù)據(jù)表T，查詢Q形如Select Count(*) fromTWherexina。若屬性x為數(shù)值型數(shù)據(jù)，該查詢統(tǒng)計(jì)屬性x的取值頻數(shù)，其中a為屬性x的1個取值。若屬性x為分類屬性，該查詢分別統(tǒng)計(jì)屬性x的類別計(jì)數(shù)，此時a為屬性x的1個類別。

例1統(tǒng)計(jì)某購物籃商品A,B,C,D的購買頻數(shù)，每個商品的購買屬性取值為0或1，0為沒有購買，1為購買。表1為商品統(tǒng)計(jì)結(jié)果，表2為對表1的統(tǒng)計(jì)結(jié)果加噪后的結(jié)果。

Table 1 Commodity statistics results表1 商品統(tǒng)計(jì)結(jié)果

Table 2 Results after adding noise 表2 加噪后的結(jié)果

假設(shè)用戶對原始表提出查詢Select Count(*) fromTWhereGoodsin (‘A’,‘B’)，即查詢商品A和B的計(jì)數(shù)和，故該查詢可稱為區(qū)間查詢，可利用表1得此查詢的精確結(jié)果為4。若利用表2來回答用戶的查詢，查詢區(qū)間較大時，即Goods的查詢類別較多時，噪聲的累加使數(shù)據(jù)的精確度降低。

由敏感度定義可知，1對兄弟表統(tǒng)計(jì)差異值為1，此時統(tǒng)計(jì)直方圖的敏感度Δf=1，若對原始數(shù)據(jù)每條記錄都添加噪聲，由于每個元素的Laplace噪聲為方差2λ2，在最壞查詢情況下，區(qū)間查詢Q覆蓋了所有的記錄，將由類似表2的加噪查詢結(jié)果中的n個元素方差相加而成，可得查詢Q的噪聲方差為O(nλ2)；當(dāng)查詢的區(qū)間較大時，將使添加噪聲后的差分隱私統(tǒng)計(jì)直方圖發(fā)布結(jié)果的方差增大，影響數(shù)據(jù)發(fā)布的有效性。據(jù)此，文獻(xiàn)[15]提出將統(tǒng)計(jì)直方圖轉(zhuǎn)化為區(qū)間樹，再對區(qū)間樹進(jìn)行差分隱私統(tǒng)計(jì)直方圖發(fā)布，當(dāng)進(jìn)行查詢時，每個父節(jié)點(diǎn)的值均為其k個子節(jié)點(diǎn)的值之和，其中k為區(qū)間樹中每個父節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)，故查詢Q的噪聲為所覆蓋節(jié)點(diǎn)的噪聲總和，且在所添加噪聲為同方差的條件下，查詢Q的噪聲方差為O(kλ2logn)?？梢姡脜^(qū)間樹發(fā)布統(tǒng)計(jì)直方圖可以大幅減少計(jì)數(shù)查詢的誤差。

定義6(滿k-叉區(qū)間樹) 將區(qū)間查詢Q的值映射到1棵k-叉樹(k≥2)的各個節(jié)點(diǎn)上，生成滿k-叉區(qū)間樹H，使得每個節(jié)點(diǎn)所對應(yīng)的查詢區(qū)間覆蓋其k個孩子節(jié)點(diǎn)的查詢區(qū)間，且每個節(jié)點(diǎn)的真實(shí)區(qū)間查詢計(jì)數(shù)值為其孩子節(jié)點(diǎn)的真實(shí)計(jì)數(shù)值之和。其中同一層節(jié)點(diǎn)的查詢區(qū)間不相交。

例2將表1中的區(qū)間查詢構(gòu)造成1棵滿2-叉區(qū)間樹H。假設(shè)查詢的區(qū)間序列為T=([A],[B],[C],[D],[AB],[CD],[ABCD])，其中區(qū)間[AB]表示查詢覆蓋商品A和B的計(jì)數(shù)和，且每個區(qū)間查詢彼此相互獨(dú)立，區(qū)間數(shù)|T|=7，令k=2，則m=3。因區(qū)間[AB],[CD],[ABCD]的計(jì)數(shù)分別為4,24和28，根據(jù)映射關(guān)系可構(gòu)造深度為3的滿2-叉區(qū)間樹H，如圖1所示。

Figure 1 Full 2-ary range tree H圖1 滿2-叉區(qū)間樹H

(5)

4 算法模型

為解決上述的不一致現(xiàn)象，文獻(xiàn)[15]提出局部最優(yōu)線性無偏估計(jì)，但只限定深度為2且有k個子節(jié)點(diǎn)的差分隱私區(qū)間樹(本文中規(guī)定樹的層數(shù)l從1開始計(jì)數(shù)，即定義1個節(jié)點(diǎn)所在的層數(shù)為葉節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的節(jié)點(diǎn)數(shù))。本文的目的是在深度大于2的滿k-叉區(qū)間樹中找到所有節(jié)點(diǎn)值的最優(yōu)線性無偏估計(jì)。

根據(jù)文獻(xiàn)[15]，假設(shè)任意1棵深度為2的區(qū)間樹H，為H中每個節(jié)點(diǎn)值隨機(jī)添加獨(dú)立同方差的Laplace(Δf/ε)噪聲，得到差分隱私區(qū)間樹。根據(jù)高斯-馬爾科夫定理，求最優(yōu)線性無偏估計(jì)等價于求解1個滿足限定條件的最小二乘解，令第i個子節(jié)點(diǎn)原始計(jì)數(shù)值為真實(shí)值Xi，則父節(jié)點(diǎn)t和子節(jié)點(diǎn)i=Son(t)={i1,i2,…,ik}添加噪聲后的節(jié)點(diǎn)值分別為：

(6)

(7)

令z表示節(jié)點(diǎn)的無偏估計(jì)權(quán)值，即得到定理1。

定理1[15](局部最優(yōu)線性無偏估計(jì)) 對于任意1棵深度m=2的差分隱私k-叉區(qū)間樹，其節(jié)點(diǎn)的最優(yōu)線性無偏估計(jì)為：

(8)

(9)

其中，

(10)

父節(jié)點(diǎn)的無偏估計(jì)值為父節(jié)點(diǎn)噪聲值減去偏差值Δ，葉節(jié)點(diǎn)的估計(jì)值為葉節(jié)點(diǎn)噪聲值加上偏差值Δ。

定理1并不適用深度大于2的差分隱私區(qū)間樹，文獻(xiàn)[15]提出迭代定理1得到局部最優(yōu)線性無偏估計(jì)迭代算法LBLUE(Local Best Linear Unbiased Estimation)，但算法隨著樹的深度增加計(jì)算量增大，效率也隨之降低。因此,本文提出差分隱私區(qū)間樹的一致性查詢算法，對區(qū)間樹進(jìn)行2次遍歷，通過自頂向下的不一致估計(jì)調(diào)整，再進(jìn)行自底向上的一致性無偏估計(jì)調(diào)整，最終得到滿足一致性約束查詢的差分隱私滿k-叉區(qū)間樹。

4.1 自頂向下的不一致估計(jì)

根據(jù)定理1，若要滿足一致性約束查詢，則父節(jié)點(diǎn)(根節(jié)點(diǎn))的無偏估計(jì)值應(yīng)等于子節(jié)點(diǎn)的無偏估計(jì)值之和，即：

(11)

對于任意子節(jié)點(diǎn)i(i∈Son(t))，有：

(12)

其中，j指父節(jié)點(diǎn)t除了i以外的子節(jié)點(diǎn)，此時節(jié)點(diǎn)i的無偏估計(jì)值為：

(13)

由式(9)可知：

(14)

綜合式(10)、式(13)和式(14)，得到：

(15)

(16)

(17)

即

(18)

因此根據(jù)自頂向下策略，可得滿k-叉區(qū)間樹各節(jié)點(diǎn)不一致有偏估計(jì)值的遞歸關(guān)系為：

(19)

自頂向下的不一致估計(jì)TDICE(Top-Down Inconsistent Estimates)算法如算法1所示。

算法1TDICE

輸出：Z(自頂向下的不一致估計(jì)的TDICE滿k-叉區(qū)間樹)。

4 返回Z

5 end

4.2 自底向上一致性估計(jì)

(20)

(21)

由式(21)可知：

(22)

則

(23)

將式(23)代入式(20)，可得：

(24)

(25)

自底向上一致性估計(jì)BUCE(Bottom-Up Consistent Estimates)算法如算法2所示。

算法2BUCE

輸入：Z。

1 將Z自底向上一致性估計(jì)；

5 end

4.3 一致性調(diào)整

在將查詢Q的計(jì)數(shù)值映射到1棵k-叉區(qū)間樹上時，可能形成完全k-叉區(qū)間樹，從而不滿足滿k-叉區(qū)間樹的要求。假設(shè)針對第2層父節(jié)點(diǎn)t，|Son(t)|表示節(jié)點(diǎn)t的子節(jié)點(diǎn)(葉節(jié)點(diǎn))的個數(shù)，第1層的葉節(jié)點(diǎn)i(i∈Son(t))，若0≤|Son(t)|≤k，則為該父節(jié)點(diǎn)t增加k-|Son(t)|個葉節(jié)點(diǎn)，賦值為0，為了與實(shí)際0值加以區(qū)別，在算法中使用‘*’進(jìn)行標(biāo)記。在經(jīng)過一致性調(diào)整后，再將所添加含有‘*’標(biāo)記的葉節(jié)點(diǎn)估計(jì)值刪除。

一致性調(diào)整算法CA描述如算法3所示。

算法3CA

輸入：Q，隱私預(yù)算ε。

1 將Q映射到滿k-叉區(qū)間樹上，add 0*to空節(jié)點(diǎn)，得到H；

5 刪除所有標(biāo)記0*的節(jié)點(diǎn)；

4.4 一致性分析

在使用CA算法之前，已經(jīng)對查詢結(jié)果添加了符合Laplace分布的噪聲，數(shù)據(jù)的隱私程度不需要再進(jìn)行討論，接下來分析CA算法的一致性。

(26)

根據(jù)式(21)和式(23)，可得：

(27)

則有

(28)

所以，經(jīng)過調(diào)整后的滿k-叉區(qū)間樹對于任一父節(jié)點(diǎn)t滿足一致性區(qū)間查詢。得證。

□

4.5 算法分析

將區(qū)間查詢的值映射到1棵滿k-叉區(qū)間樹上，設(shè)滿k-叉區(qū)間樹的節(jié)點(diǎn)總個數(shù)為n。算法1是將1棵添加噪聲后的滿k-叉區(qū)間樹進(jìn)行1次自頂向下的遍歷，時間復(fù)雜度為O(n)；而算法2是將1棵自頂向下不一致估計(jì)后的滿k-叉區(qū)間樹進(jìn)行1次自底向上的一致性估計(jì)，時間復(fù)雜度也為O(n)。因此，CA算法的總時間復(fù)雜度為O(n)。

5 實(shí)驗(yàn)評估

本節(jié)主要驗(yàn)證一致性調(diào)整后的直方圖發(fā)布滿足一致性且精確度高，以及算法的時間效率高于需迭代的LBLUE算法的。4.4節(jié)已證明一致性調(diào)整后的數(shù)據(jù)滿足一致性約束查詢，因此根據(jù)精確度和時間效率進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)對比分析對象為在滿k-叉區(qū)間樹上添加符合Laplace分布的噪聲值實(shí)現(xiàn)差分隱私算法H～,對比算法為文獻(xiàn)[7]Boost-2算法、文獻(xiàn)[15]LBLUE算法和一致性調(diào)整算法CA。

實(shí)驗(yàn)采用的數(shù)據(jù)集為：Amazon[15]和Nettrace[7]。其中Amazon是為期1 894天的用戶對亞馬遜網(wǎng)站發(fā)起請求操作的時間數(shù)據(jù)集,Nettrace是1所大學(xué)65 535條內(nèi)聯(lián)網(wǎng)的IP地址軌跡數(shù)據(jù)。

實(shí)驗(yàn)環(huán)境為2.60 GHz Intel(R)Core(TM)i5-3230M CPU，4.00 GB內(nèi)存，Windows 10專業(yè)版64位操作系統(tǒng)，數(shù)據(jù)分析軟件為IBM SPSS Statistics 22，編程軟件為Eclipse 4.3，繪制結(jié)果分析圖軟件為Matlab R2016a。

5.1 區(qū)間查詢精確度對比

采用均方誤差MSE[12]度量精確度。在區(qū)間查詢精確度對比實(shí)驗(yàn)中，通過改變區(qū)間查詢的大小，在每個區(qū)間內(nèi)隨機(jī)選取500個查詢，得到這些區(qū)間查詢的均方誤差，然后求取均值來確定區(qū)間查詢的精確度。隱私預(yù)算ε分別取值0.01和1.0進(jìn)行實(shí)驗(yàn)，分析結(jié)果如圖2和圖3所示。

Figure 2 MSE changes of different range queries on Amazon dataset圖2 Amazon數(shù)據(jù)集下不同的區(qū)間查詢MSE變化

Figure 3 MSE changes of different range queries on Nettrace dataset圖3 Nettrace數(shù)據(jù)集下不同的區(qū)間查詢MSE變化

圖2為使用Amazon數(shù)據(jù)集的分析結(jié)果，圖3為使用Nettrace數(shù)據(jù)集的分析結(jié)果?？梢悦黠@看到，即使ε取值不同，相同區(qū)間查詢，H～得到的結(jié)果誤差最大。在圖2a中ε=0.01時，區(qū)間查詢的誤差值約為103，在圖2b中ε=1.0時，區(qū)間查詢的誤差值約為101，幾乎接近于真實(shí)值。而在圖3a中ε=0.01時，區(qū)間查詢的誤差值約為106，在圖3b中ε=1.0時，區(qū)間查詢的誤差值約為102。這是因?yàn)镹ettrace數(shù)據(jù)集相比Amazon數(shù)據(jù)集，單位長度區(qū)間個數(shù)更多，因此誤差值數(shù)量級相差更大。

對比分析圖2和圖3可得，同一數(shù)據(jù)集下，ε取值越大，均方誤差值越小，即數(shù)據(jù)的可用性越高。因?yàn)殡S著區(qū)間值增大，區(qū)間查詢樹的節(jié)點(diǎn)個數(shù)越多，需要添加噪聲值的節(jié)點(diǎn)數(shù)越多，導(dǎo)致均方誤差值越大。而H～為直接向滿k-叉區(qū)間樹中添加噪聲得到的結(jié)果，與其他3種經(jīng)過調(diào)整后的算法對比，均方誤差值明顯更大。Boost-2算法的均方誤差值比LBLUE算法的誤差值小，這與文獻(xiàn)[15]得出的分析結(jié)果相同。因CA算法不需要迭代，只需要對區(qū)間樹進(jìn)行2次遍歷，所以噪聲值的疊加也會減小，相比Boost-2算法和LBLUE算法均方誤差值有所減少。

5.2 算法時間效率對比

通過使用Amazon數(shù)據(jù)集和Nettrace數(shù)據(jù)集對比Boost-2算法、LBLUE算法、CA算法的運(yùn)行時間，分別取ε=0.01，0.1，1.0進(jìn)行實(shí)驗(yàn)。從圖4中可以明顯看到，不論ε取何值，同一數(shù)據(jù)集下相同算法的運(yùn)行時間相同，因此得出結(jié)論：算法運(yùn)行時間與ε取值的大小無關(guān)。還可以看出，在2個數(shù)據(jù)集對比圖中，Boost-2算法和CA算法的運(yùn)行時間基本相同，而LBLUE算法的運(yùn)行時間明顯較長，這是因?yàn)長BLUE算法需要迭代運(yùn)行，而其他2種算法不需要迭代運(yùn)行，因此運(yùn)行時間比LBLUE算法的短。而數(shù)據(jù)集的大小不同，運(yùn)行時間也不同，即數(shù)據(jù)集記錄條數(shù)越多，算法的運(yùn)行時間越大?？傮w而言，在同一數(shù)據(jù)集下，本文算法的運(yùn)行效率高于LBLUE算法的運(yùn)行效率。

Figure 4 Comparison of the average running time of three algorithms with different ε圖4 3種算法在ε不同時平均運(yùn)行時間的比較

6 結(jié)束語

本文針對直方圖發(fā)布區(qū)間查詢的不一致問題，提出一致性調(diào)整算法CA。先將滿k-叉區(qū)間樹進(jìn)行自頂向下的不一致估計(jì)TDICE，然后對不一致估計(jì)后的結(jié)果進(jìn)行自底向上一致性估計(jì)BUCE，得到一致性調(diào)整(CA)后的結(jié)果。經(jīng)證明，通過一致性調(diào)整后的滿k-叉區(qū)間樹滿足一致性約束查詢。使用真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對比，得出一致性調(diào)整(CA)后的區(qū)間查詢精確度較高且時間效率高于LBLUE算法的。此外，當(dāng)數(shù)據(jù)集較大時，如何降低區(qū)間查詢誤差值是下一步需要進(jìn)行的工作。