葛 晨，吳英杰，孫 嵐

福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州 350116

1 引言

當(dāng)前，許多應(yīng)用受益于流數(shù)據(jù)的連續(xù)統(tǒng)計(jì)監(jiān)測(cè)，如基于位置的服務(wù)通過(guò)實(shí)時(shí)的統(tǒng)計(jì)信息向用戶(hù)推薦商店，社交網(wǎng)絡(luò)通過(guò)實(shí)時(shí)地統(tǒng)計(jì)用戶(hù)來(lái)獲得熱門(mén)話題，這些應(yīng)用均需用到流數(shù)據(jù)的實(shí)時(shí)統(tǒng)計(jì)值。然而，這類(lèi)數(shù)據(jù)的發(fā)布在為用戶(hù)帶來(lái)便利的同時(shí)，還可能伴隨著泄露用戶(hù)敏感隱私信息的風(fēng)險(xiǎn)[1]。

近年來(lái)，基于差分隱私[2-5]保護(hù)模型的流數(shù)據(jù)隱私保護(hù)已成為一個(gè)熱門(mén)的研究方向[6-10]。流數(shù)據(jù)的差分隱私保護(hù)問(wèn)題最早由Dwork等人[6]提出，使用分段計(jì)數(shù)的發(fā)布方法實(shí)現(xiàn)單條流數(shù)據(jù)的連續(xù)統(tǒng)計(jì)發(fā)布。Chan等人[7]基于區(qū)間樹(shù)結(jié)構(gòu)實(shí)現(xiàn)了無(wú)限長(zhǎng)度流數(shù)據(jù)的連續(xù)統(tǒng)計(jì)發(fā)布，同時(shí)提升了查詢(xún)精度和算法效率。Cao等人[8]通過(guò)對(duì)歷史查詢(xún)集合進(jìn)行分析，有效提高了用戶(hù)批量查詢(xún)的查詢(xún)精度。Bolot等人[9]針對(duì)數(shù)據(jù)項(xiàng)帶有權(quán)重的情形,提出權(quán)重衰減模型下的流數(shù)據(jù)發(fā)布模型。文獻(xiàn)[10]基于數(shù)據(jù)抽樣和滑動(dòng)窗口機(jī)制提出一種面向流式直方圖的差分隱私發(fā)布方法．文獻(xiàn)[11]利用區(qū)間樹(shù)實(shí)現(xiàn)滑動(dòng)窗口下面向任意區(qū)間查詢(xún)的統(tǒng)計(jì)發(fā)布，并利用歷史查詢(xún)調(diào)整樹(shù)結(jié)構(gòu)以提高查詢(xún)精度。以上研究工作主要聚焦在如何提高發(fā)布流數(shù)據(jù)的查詢(xún)精度，而許多實(shí)際應(yīng)用的發(fā)布過(guò)程需要進(jìn)行大量的實(shí)時(shí)查詢(xún)，如購(gòu)物網(wǎng)站在推薦商品時(shí)，需要獲取商品在不同時(shí)段的實(shí)時(shí)銷(xiāo)售額，從而進(jìn)行有效推薦，該應(yīng)用將對(duì)算法的查詢(xún)效率有著較高的要求。本文將針對(duì)該類(lèi)流數(shù)據(jù)發(fā)布應(yīng)用提出一種高查詢(xún)效率的實(shí)時(shí)發(fā)布方法，同時(shí)使查詢(xún)精度無(wú)明顯降低。

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

（1）針對(duì)流數(shù)據(jù)應(yīng)用中存在需要大量實(shí)時(shí)查詢(xún)的情形，提出一種支持高效查詢(xún)的流數(shù)據(jù)實(shí)時(shí)發(fā)布方法。

（2）利用矩陣在處理關(guān)聯(lián)性查詢(xún)方面的優(yōu)勢(shì)，在查詢(xún)效率量級(jí)不變的前提下利用對(duì)角矩陣優(yōu)化進(jìn)一步提高發(fā)布方法的查詢(xún)精度。

（3）通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證本文方法的有效性與可行性。

2 基礎(chǔ)知識(shí)與相關(guān)定義

2.1 差分隱私定義

Dwork等人首次提出了差分隱私模型[2]，該模型是一種強(qiáng)健的隱私保護(hù)框架，通過(guò)減少修改數(shù)據(jù)集中一條記錄對(duì)查詢(xún)結(jié)果的影響，使得攻擊者即使知道了除某條記錄外的所有記錄信息，也無(wú)法準(zhǔn)確獲得該條記錄中的敏感信息。

定義1（兄弟數(shù)據(jù)集）給定數(shù)據(jù)集D、D′，當(dāng)兩個(gè)數(shù)據(jù)集之間只相差一條記錄時(shí)，即：

則稱(chēng)D、D′為兄弟數(shù)據(jù)集，其中表示數(shù)據(jù)集中記錄的數(shù)量。

定義2（ε-差分隱私）對(duì)于給定的兩個(gè)兄弟數(shù)據(jù)集D1、D2，若發(fā)布算法A對(duì)該對(duì)兄弟數(shù)據(jù)集的所有可能輸出O?range(A)均滿(mǎn)足：

則稱(chēng)算法A滿(mǎn)足ε-差分隱私。

定義3（敏感度）對(duì)某數(shù)據(jù)庫(kù)中的數(shù)據(jù)集D和D′分別進(jìn)行統(tǒng)計(jì)，得到兩組由列向量表示的統(tǒng)計(jì)結(jié)果：。那么查詢(xún)集Q的敏感度ΔQ定義如下：

其中，xi表示查詢(xún)的結(jié)果。

2.2 差分隱私流數(shù)據(jù)區(qū)間計(jì)數(shù)查詢(xún)

定義4（流數(shù)據(jù)）流數(shù)據(jù)是一組順序、大量、快速、連續(xù)到達(dá)的數(shù)據(jù)序列。一般情況下，流數(shù)據(jù)可被視為一個(gè)隨時(shí)間延續(xù)而無(wú)限增長(zhǎng)的動(dòng)態(tài)數(shù)據(jù)集合。

利用區(qū)間樹(shù)可以有效提高數(shù)據(jù)的發(fā)布精度，但是在流數(shù)據(jù)的背景中隨著數(shù)據(jù)的逐漸增加，會(huì)使得隱私預(yù)算耗盡而降低數(shù)據(jù)的隱私保護(hù)程度。Chan等人[7]根據(jù)實(shí)際應(yīng)用背景，利用滑動(dòng)窗口機(jī)制來(lái)發(fā)布流數(shù)據(jù)，避免了隱私預(yù)算耗盡的問(wèn)題。

定義5（滑動(dòng)窗口下的流數(shù)據(jù)區(qū)間計(jì)數(shù)查詢(xún)）設(shè)當(dāng)前數(shù)據(jù)序列的時(shí)序?yàn)閠，數(shù)據(jù)序列為S={C1,C2,…,Ct}，用戶(hù)提出的查詢(xún)操作為q，查詢(xún)操作定義為在滑動(dòng)窗口內(nèi)的某段連續(xù)統(tǒng)計(jì)計(jì)數(shù)值的累加和查詢(xún)，查詢(xún)操作q的查詢(xún)范圍為[lq,rq](t-W＜lq≤rq≤t)，而相應(yīng)的查詢(xún)結(jié)果可由如下公式表示：

滑動(dòng)窗口下的流數(shù)據(jù)發(fā)布如圖1所示。

Fig.1 Streaming data in sliding window圖1 滑動(dòng)窗口下的流數(shù)據(jù)發(fā)布

流數(shù)據(jù)下的差分隱私保護(hù)分為兩個(gè)層面[6]，一個(gè)是事件層的隱私保護(hù)，一個(gè)是用戶(hù)層的隱私保護(hù)。事件層的隱私保護(hù)是保護(hù)流數(shù)據(jù)序列中的每一個(gè)事件，而用戶(hù)層的保護(hù)則是保護(hù)用戶(hù)的所有行為，用戶(hù)會(huì)有多個(gè)行為，這些行為可以組成多個(gè)事件。本文針對(duì)的是事件層的隱私保護(hù)，保護(hù)流數(shù)據(jù)序列中的每一個(gè)事件。

3 滑動(dòng)窗口下的差分隱私流數(shù)據(jù)實(shí)時(shí)發(fā)布

本章主要介紹基于滑動(dòng)窗口的樹(shù)結(jié)構(gòu)模型構(gòu)建，給出復(fù)雜度為O(n)的實(shí)時(shí)發(fā)布方法，同時(shí)在此框架下利用矩陣機(jī)制提高發(fā)布數(shù)據(jù)的查詢(xún)精度而不降低查詢(xún)效率。

3.1 模型構(gòu)建

利用區(qū)間樹(shù)構(gòu)建差分隱私發(fā)布模型，可以提高數(shù)據(jù)發(fā)布的效率，從而適應(yīng)流數(shù)據(jù)的實(shí)效性要求。在文獻(xiàn)[7]中，其通過(guò)完全二叉樹(shù)的結(jié)構(gòu)來(lái)組織表示與發(fā)布數(shù)據(jù)，其具體表示形式如圖2所示。

Fig.2 Construction process of interval tree in sliding window圖2 滑動(dòng)窗口下的區(qū)間樹(shù)構(gòu)建過(guò)程

設(shè)滑動(dòng)窗口大小為|W|，當(dāng)前時(shí)刻為t。如圖2中所示，滑動(dòng)窗口內(nèi)各包含兩棵二叉樹(shù)的一部分。其中，灰色節(jié)點(diǎn)已滑出滑動(dòng)窗口，在之后查詢(xún)發(fā)布中不再涉及這些節(jié)點(diǎn)，而條紋節(jié)點(diǎn)為即將使用的節(jié)點(diǎn)，在樹(shù)中第一個(gè)節(jié)點(diǎn)進(jìn)入滑動(dòng)窗口時(shí)整棵二叉樹(shù)中的所有節(jié)點(diǎn)已經(jīng)預(yù)先建立，隨著逐步進(jìn)入滑動(dòng)窗口，這些節(jié)點(diǎn)將相應(yīng)地被激活。

在完全二叉樹(shù)的構(gòu)建方法中，對(duì)于單次查詢(xún)而言，其查詢(xún)時(shí)間復(fù)雜度為O(lbn)，與樹(shù)的高度相關(guān)，當(dāng)滑動(dòng)窗口大小較大且每一個(gè)時(shí)刻需求大量查詢(xún)時(shí)，其耗時(shí)較多?？梢酝ㄟ^(guò)對(duì)頻繁查詢(xún)的區(qū)間進(jìn)行存儲(chǔ)，但是其提升效率的同時(shí)將造成大量的內(nèi)存開(kāi)銷(xiāo)。本文將通過(guò)去除完全二叉樹(shù)中的部分節(jié)點(diǎn)，實(shí)現(xiàn)連續(xù)統(tǒng)計(jì)發(fā)布，并通過(guò)連續(xù)統(tǒng)計(jì)的發(fā)布值得到滑動(dòng)窗口內(nèi)任意區(qū)間查詢(xún)的計(jì)數(shù)值，使其單次查詢(xún)的時(shí)間復(fù)雜度降為O(1)。其表示如圖3所示。

通過(guò)圖3中的二叉樹(shù)結(jié)果，可以提供樹(shù)中任意區(qū)間的查詢(xún)計(jì)數(shù)值。但是對(duì)于連續(xù)統(tǒng)計(jì)而言，樹(shù)中的虛線節(jié)點(diǎn)是不必要的，樹(shù)中每個(gè)右子節(jié)點(diǎn)的信息將保存在其父節(jié)點(diǎn)中。假設(shè)滑動(dòng)窗口的大小為W，則樹(shù)中需要保存的節(jié)點(diǎn)也為W，因此根據(jù)樹(shù)中的節(jié)點(diǎn)關(guān)系，可以在O(1)時(shí)間內(nèi)計(jì)算出當(dāng)前連續(xù)統(tǒng)計(jì)過(guò)程中涉及的最新節(jié)點(diǎn)。

Fig.3 Dynamic construction process of interval tree in sliding window圖3 滑動(dòng)窗口中的區(qū)間樹(shù)動(dòng)態(tài)構(gòu)建過(guò)程

樹(shù)狀數(shù)組是一個(gè)對(duì)于查詢(xún)和修改的時(shí)間復(fù)雜度均為O(lbN)的數(shù)據(jù)結(jié)構(gòu)，對(duì)于給定的r，可以快速求得區(qū)間[1,r]的和值。設(shè)區(qū)間[1,r]的和為Sum(r)，即。

樹(shù)狀數(shù)組在計(jì)算過(guò)程中，生成了中間統(tǒng)計(jì)量Si(i∈[1,r])，如下：

其中，Dj表示第j個(gè)數(shù)的值,lowbit(x)將x表示二進(jìn)制后，只保留其最低位的1的對(duì)應(yīng)值。以x=12為例，(12)10=(1100)2，最低位的1為右數(shù)第三位，則lowbit(x)=(0100)2=(4)10。通過(guò)補(bǔ)碼性質(zhì)可知，lowbit(x)=x&(-x)。而后，樹(shù)狀數(shù)組通過(guò)中間統(tǒng)計(jì)量Si，得到區(qū)間和值如下：

按照時(shí)序?qū)Ξ?dāng)前時(shí)刻涉及的節(jié)點(diǎn)進(jìn)行編號(hào)，可將圖3中的實(shí)線節(jié)點(diǎn)表示為樹(shù)狀數(shù)組，如圖4所示，其中①～④為一棵樹(shù)，⑤～⑦為另一棵樹(shù)，樹(shù)的大小不應(yīng)超過(guò)滑動(dòng)窗口大小以導(dǎo)致存儲(chǔ)冗余節(jié)點(diǎn)。實(shí)節(jié)點(diǎn)左邊的數(shù)字為其節(jié)點(diǎn)編號(hào)，其中節(jié)點(diǎn)①的值為t1時(shí)刻的統(tǒng)計(jì)值，節(jié)點(diǎn)②為t1與t2時(shí)刻的統(tǒng)計(jì)值的和，節(jié)點(diǎn)③的值為t3時(shí)刻的統(tǒng)計(jì)值，節(jié)點(diǎn)④為t1～t4時(shí)刻的統(tǒng)計(jì)值的和值。由于父節(jié)點(diǎn)表示為其所有子節(jié)點(diǎn)的累加和值（對(duì)于給定的x，如果x+lowbit(x)等于y，則把編號(hào)為x的節(jié)點(diǎn)稱(chēng)為y的子節(jié)點(diǎn)，編號(hào)為y的節(jié)點(diǎn)稱(chēng)為x對(duì)應(yīng)的父節(jié)點(diǎn)），每個(gè)節(jié)點(diǎn)其對(duì)應(yīng)的父節(jié)點(diǎn)是唯一的，因此每個(gè)節(jié)點(diǎn)只會(huì)參與一次累加過(guò)程，即對(duì)于節(jié)點(diǎn)④而言，其值為節(jié)點(diǎn)②的值、節(jié)點(diǎn)③的值與t4時(shí)刻的實(shí)際統(tǒng)計(jì)值之和，同時(shí)節(jié)點(diǎn)②與節(jié)點(diǎn)③的值只會(huì)在節(jié)點(diǎn)④的計(jì)算過(guò)程中使用到，可以在計(jì)算節(jié)點(diǎn)②時(shí)，為節(jié)點(diǎn)④預(yù)先開(kāi)辟空間，與此同時(shí)將節(jié)點(diǎn)②的值累加到節(jié)點(diǎn)④上，而節(jié)點(diǎn)⑤～⑦在另一棵樹(shù)中，其計(jì)算過(guò)程與節(jié)點(diǎn)①～③的計(jì)算過(guò)程相同，因此在建樹(shù)過(guò)程中，時(shí)間復(fù)雜度是線性的。

Fig.4 Construction process of tree array圖4 樹(shù)狀數(shù)組建樹(shù)過(guò)程

連續(xù)統(tǒng)計(jì)發(fā)布過(guò)程中可使用如圖4所示的樹(shù)結(jié)構(gòu)，區(qū)間[1，1]的值為節(jié)點(diǎn)①的值，區(qū)間[1，2]的值為節(jié)點(diǎn)②的值，區(qū)間[1，3]的值為節(jié)點(diǎn)②與節(jié)點(diǎn)③的和，區(qū)間[1，5]的值由于橫跨兩棵樹(shù)，其值為節(jié)點(diǎn)④與節(jié)點(diǎn)⑤的和值，其余節(jié)點(diǎn)與上述節(jié)點(diǎn)計(jì)算過(guò)程相同?？紤]在同一棵樹(shù)中的發(fā)布過(guò)程中，對(duì)于時(shí)刻t7而言，將7表示為二進(jìn)制111，則時(shí)刻t7的發(fā)布值為節(jié)點(diǎn)⑦的值、節(jié)點(diǎn)⑥的值與節(jié)點(diǎn)④的值的和，而時(shí)刻t6的發(fā)布值為節(jié)點(diǎn)⑥的值與節(jié)點(diǎn)④的值的和，因此t7時(shí)刻的發(fā)布值可以表示為時(shí)刻t6的發(fā)布值與節(jié)點(diǎn)⑦的值的和。因此對(duì)于單次查詢(xún)而言，其時(shí)間復(fù)雜度為O(1)。

Fig.5 Insert node and create new tree圖5 節(jié)點(diǎn)插入，建立新樹(shù)

滑動(dòng)窗口在移動(dòng)過(guò)程中如圖5所示，首先根據(jù)預(yù)先設(shè)置的滑動(dòng)窗口大小，選擇合適的樹(shù)高，使得樹(shù)的大小不會(huì)超出滑動(dòng)窗口大小。圖5中滑動(dòng)窗口大小為5，因此可以預(yù)先定義樹(shù)高為3。在圖5中，移出滑動(dòng)窗口的過(guò)期節(jié)點(diǎn)將不再使用而被回收，減少存儲(chǔ)開(kāi)銷(xiāo)。同時(shí)在完成一棵樹(shù)之后，新到達(dá)的節(jié)點(diǎn)會(huì)根據(jù)設(shè)置好的樹(shù)高，構(gòu)建一棵新的待完成的樹(shù)。

對(duì)于給定的滑動(dòng)窗口大小W，其樹(shù)高也為之確定，假設(shè)其為H，根據(jù)式（3）可得其敏感度為H，因此對(duì)于樹(shù)中的每一個(gè)節(jié)點(diǎn)添加噪聲規(guī)模為H的Laplace噪聲[12]，可以使得算法滿(mǎn)足ε-差分隱私。

具體算法過(guò)程如下：

算法1節(jié)點(diǎn)插入算法Insert

算法2滑動(dòng)窗口下的任意區(qū)間查詢(xún)實(shí)時(shí)發(fā)布算法RTP

3.2 利用矩陣機(jī)制優(yōu)化查詢(xún)精度

由于在連續(xù)統(tǒng)計(jì)發(fā)布過(guò)程中無(wú)法實(shí)現(xiàn)任意區(qū)間的查詢(xún)，因此需要通過(guò)連續(xù)統(tǒng)計(jì)的發(fā)布值來(lái)獲得。例如，在圖4中，區(qū)間[2，5]的和需要通過(guò)[1，4]+[4，5]-[1，2]的值來(lái)得到，因此會(huì)涉及到已發(fā)布結(jié)果中的多個(gè)統(tǒng)計(jì)值，造成噪聲的累加，使得查詢(xún)精度下降。但是，連續(xù)統(tǒng)計(jì)發(fā)布過(guò)程設(shè)定了特殊的查詢(xún)區(qū)間[1，t]，因此可以通過(guò)查詢(xún)和查詢(xún)間的關(guān)聯(lián)性來(lái)降低誤差，并且不降低其查詢(xún)效率。

樹(shù)狀數(shù)組生成中間變量的過(guò)程可以通過(guò)矩陣與向量相乘的形式表示，當(dāng)r=7時(shí)，其表示形式如下：

其中，L表示策略矩陣，D表示原始數(shù)據(jù)集，S表示中間變量向量，即通過(guò)策略矩陣將數(shù)據(jù)表示為中間變量的形式，添加噪聲后再利用矩陣將其還原為查詢(xún)結(jié)果。式（7）表示將原始發(fā)布值轉(zhuǎn)換為圖3中樹(shù)結(jié)構(gòu)中實(shí)節(jié)點(diǎn)的過(guò)程。

同時(shí)，當(dāng)樹(shù)結(jié)構(gòu)確定后，即可通過(guò)式（6）將其還原成為需要的連續(xù)統(tǒng)計(jì)發(fā)布值，當(dāng)r=7時(shí)，用矩陣表示其形式如下：

其中，W表示查詢(xún)的負(fù)載矩陣。在連續(xù)統(tǒng)計(jì)發(fā)布背景中，其形式如下：

即連續(xù)統(tǒng)計(jì)發(fā)布結(jié)果可以表示為WD=BLD，且W=BL。

在將樹(shù)結(jié)構(gòu)轉(zhuǎn)換為矩陣形式后，本文方法可以作為矩陣機(jī)制的一種特殊分解策略。矩陣機(jī)制是通過(guò)將負(fù)載矩陣W進(jìn)行矩陣分解，得到一種最優(yōu)的分解策略，以提高數(shù)據(jù)的發(fā)布精度。本文則是設(shè)計(jì)一種特殊形式的矩陣分解策略，誤差高于矩陣機(jī)制中的最優(yōu)分解策略，但是其可以通過(guò)樹(shù)狀數(shù)組的方式快速求解，從而滿(mǎn)足流數(shù)據(jù)的實(shí)時(shí)性要求。根據(jù)文獻(xiàn)[13]的結(jié)論，其均方誤差為：

假設(shè)數(shù)據(jù)規(guī)模為N，根據(jù)式（6）可得到還原矩陣B中每一行的非零元素個(gè)數(shù)不大于lbN個(gè)，而推出矩陣B的非零元素個(gè)數(shù)不大于NlbN。由于矩陣B中的非零元素只有1，因此trace(BTB)≤NlbN。根據(jù)式（5）可得ΔL與樹(shù)高H相同，因此ΔL=lbN，從而得到n次查詢(xún)的誤差errorL(W)=O(Nlb3N)，平均單次查詢(xún)誤差為O(lb3N)

同時(shí)，轉(zhuǎn)換為矩陣機(jī)制后，本文將通過(guò)文獻(xiàn)[14]的結(jié)論，提高其發(fā)布精度。根據(jù)其結(jié)論，存在一個(gè)對(duì)角矩陣Λ，從而使得W=BL?W=BΛΛ-1L，通過(guò)選取合適的對(duì)角矩陣，可以提高數(shù)據(jù)的發(fā)布精度。

其相應(yīng)的均方誤差變?yōu)椋?/p>

通過(guò)調(diào)整對(duì)角矩陣可以使得誤差進(jìn)一步降低，文獻(xiàn)[14]給出具體求解方法，其過(guò)程如算法3所示。

但是添加對(duì)角矩陣后Λ會(huì)使得原本的敏感度發(fā)生改變。通過(guò)將算法表示為矩陣后，可以在矩陣機(jī)制的框架下對(duì)其求解。利用矩陣機(jī)制的相關(guān)結(jié)論[13]，可以使得只要算法符合式（11）的定義，就可以使得其滿(mǎn)足ε-差分隱私。根據(jù)文獻(xiàn)[13]，矩陣機(jī)制表示如下：

其中，ΔL表示矩陣L的敏感度；表示根據(jù)給定的噪聲規(guī)模產(chǎn)生每一維均是獨(dú)立Laplace噪聲的向量。

增加對(duì)角矩陣之后，式（11）變更為：

文獻(xiàn)[14]中求解對(duì)角矩陣的方法其時(shí)間復(fù)雜度為O(lbN)，且其在無(wú)滑動(dòng)窗口約束的前提下隨著時(shí)間的推移，N的值會(huì)越來(lái)越大，使得查詢(xún)精度下降的同時(shí)降低發(fā)布效率。在滑動(dòng)窗口背景中，由于滑動(dòng)窗口大小是事先給定的，二叉樹(shù)的大小同時(shí)為之確定，因此對(duì)角矩陣系數(shù)的計(jì)算可以做為預(yù)處理的部分，在實(shí)時(shí)發(fā)布過(guò)程中直接調(diào)用預(yù)先計(jì)算好的對(duì)角矩陣系數(shù)值，不影響實(shí)時(shí)發(fā)布的查詢(xún)效率。

將樹(shù)結(jié)構(gòu)表示為矩陣后，結(jié)合對(duì)角矩陣系數(shù)優(yōu)化方法，形成算法RTP_MM，其算法過(guò)程如下：

算法3對(duì)角陣系數(shù)求解算法getLamta

算法4節(jié)點(diǎn)插入算法Insert 2

算法5基于快速對(duì)角矩陣的滑動(dòng)窗口下的任意區(qū)間查詢(xún)實(shí)時(shí)發(fā)布算法RTP_MM

4 實(shí)驗(yàn)分析

本章將從查詢(xún)效率和查詢(xún)精度兩方面對(duì)4種算法進(jìn)行實(shí)驗(yàn)比較分析來(lái)說(shuō)明本文算法的有效性，其中FDA（fast diagonal algorithm）為文獻(xiàn)[14]所提出在無(wú)滑動(dòng)窗口下利用矩陣機(jī)制的連續(xù)統(tǒng)計(jì)發(fā)布算法，RTP（real time publish）為本文僅利用樹(shù)狀數(shù)組而未利用矩陣機(jī)制進(jìn)行優(yōu)化的算法，HQ_DPSAP（historical query differential privacy streaming data adaptive publication）為文獻(xiàn)[11]所提出的基于二叉樹(shù)結(jié)構(gòu)利用歷史查詢(xún)優(yōu)化的流數(shù)據(jù)發(fā)布方法，RTP_MM（real time publish matrix mechanism）為本文利用樹(shù)狀數(shù)組并經(jīng)對(duì)角矩陣優(yōu)化的算法。LP（Laplace publish）為Dwork[2]提出的直接在每個(gè)事件統(tǒng)計(jì)值上添加Laplace噪聲的方法。為了排除隨機(jī)參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響，對(duì)每組實(shí)驗(yàn)運(yùn)行30次的結(jié)果取平均值，作為最終實(shí)驗(yàn)對(duì)比數(shù)據(jù)。

4.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

為方便對(duì)比與分析，本文采用了文獻(xiàn)[15]中的數(shù)據(jù)集NetTrace，以及文獻(xiàn)[16]中使用的WorldCup98數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)。NetTrace數(shù)據(jù)集包含了某單位在特定時(shí)間段內(nèi)對(duì)特定IP段的數(shù)據(jù)包請(qǐng)求次數(shù)。WorldCup98為1998年4月至1998年7月期間，世界杯官網(wǎng)的訪問(wèn)量的統(tǒng)計(jì)記錄。其數(shù)據(jù)規(guī)模如表1所示。

在實(shí)驗(yàn)中，采用均方誤差衡量算法發(fā)布數(shù)據(jù)的查詢(xún)精度，誤差公式如下：

Table 1 Data set表1 數(shù)據(jù)集

其中，|Q|為查詢(xún)的數(shù)量；D為原始數(shù)據(jù)集；D′為添加噪聲后的發(fā)布結(jié)果；q表示一次查詢(xún)。

實(shí)驗(yàn)環(huán)境為：Intel Core i5 4570 3.2 GHz處理器，8 GB內(nèi)存，Windows 7操作系統(tǒng)；算法用C++語(yǔ)言實(shí)現(xiàn)；由Excel生成實(shí)驗(yàn)圖表。

4.2 查詢(xún)效率的對(duì)比分析

（1）查詢(xún)次數(shù)對(duì)查詢(xún)效率的影響

本節(jié)實(shí)驗(yàn)在每時(shí)刻設(shè)置不同的查詢(xún)次數(shù)來(lái)比較4種算法的查詢(xún)效率，由于在小數(shù)據(jù)集上查詢(xún)效率變化不明顯，因此實(shí)驗(yàn)只使用WorldCup98數(shù)據(jù)集來(lái)考察查詢(xún)效率，其中查詢(xún)區(qū)間大小均設(shè)為32 768，涉及滑動(dòng)窗口的算法其窗口大小固定為65 536，實(shí)驗(yàn)結(jié)果如圖6所示。

從圖6可以看出，除了HQ_DPSAP外，利用連續(xù)統(tǒng)計(jì)發(fā)布而獲得滑動(dòng)窗口內(nèi)任意區(qū)間查詢(xún)值的算法的查詢(xún)效率基本一致。只有在查詢(xún)次數(shù)較少時(shí)有所差異，這是因?yàn)樵诓樵?xún)次數(shù)較少時(shí)，影響查詢(xún)效率的主要因素是模型構(gòu)建所花費(fèi)的時(shí)間，RTP與RTP_MM算法在模型構(gòu)建上的時(shí)間復(fù)雜度均為O(N)，因此在圖6中兩條曲線基本重合，而FDA算法的模型構(gòu)建時(shí)間復(fù)雜度[14]為O(NlbN)，因此其查詢(xún)效率要略低些；當(dāng)查詢(xún)次數(shù)增加時(shí)，占效率主導(dǎo)地位的是查詢(xún)時(shí)所花費(fèi)的時(shí)間，且隨查詢(xún)次數(shù)的增加而增加。利用連續(xù)統(tǒng)計(jì)發(fā)布結(jié)果來(lái)獲得任意區(qū)間查詢(xún)結(jié)果的算法的查詢(xún)效率為O(1)，而HQ_DPSAP通過(guò)構(gòu)建區(qū)間樹(shù)來(lái)實(shí)現(xiàn)滑動(dòng)窗口內(nèi)任意區(qū)間查詢(xún)，雖可使查詢(xún)所涉及的樹(shù)中節(jié)點(diǎn)個(gè)數(shù)較少，但由于每次查詢(xún)均要重新遍歷樹(shù)高，因此對(duì)于單次查詢(xún)而言，其時(shí)間復(fù)雜度為O(lbW)，與其滑動(dòng)窗口大小相關(guān)，故查詢(xún)效率較低。

（2）滑動(dòng)窗口大小對(duì)查詢(xún)效率的影響

本節(jié)實(shí)驗(yàn)設(shè)置不同的滑動(dòng)窗口大小來(lái)比較4種算法的查詢(xún)效率，由于在小數(shù)據(jù)集上查詢(xún)效率變換不明顯，因此實(shí)驗(yàn)只使用WorldCup98數(shù)據(jù)集來(lái)考察查詢(xún)效率，滑動(dòng)窗口大小分別設(shè)置為215,216,…,221，查詢(xún)區(qū)間大小設(shè)為滑動(dòng)窗口大小的一半，以使得查詢(xún)區(qū)間大小隨滑動(dòng)窗口增加而增加，查詢(xún)次數(shù)設(shè)為每時(shí)刻查詢(xún)一次。實(shí)驗(yàn)結(jié)果如圖7所示。

從圖7可以看出，隨著滑動(dòng)窗口大小的增加，RTP、FDA算法的影響最小，滑動(dòng)窗口只影響RTP算法的空間大小，而對(duì)于FDA算法而言，查詢(xún)效率只與流數(shù)據(jù)的預(yù)設(shè)大小相關(guān)，與滑動(dòng)窗口大小無(wú)關(guān)。對(duì)于RTP_MM算法而言，滑動(dòng)窗口會(huì)影響其預(yù)處理的時(shí)間，而與查詢(xún)無(wú)關(guān)，而HQ_DPSAP算法的查詢(xún)效率是O(lbW)，因此隨著滑動(dòng)窗口大小的增加，其查詢(xún)時(shí)間會(huì)逐步增加，因此RTP、FDA、RTP_MM算法均位于其下方。

4.3 查詢(xún)精度的對(duì)比分析

實(shí)驗(yàn)將在Nettrace、WorldCup98兩個(gè)數(shù)據(jù)集上進(jìn)行滑動(dòng)窗口下的任意區(qū)間查詢(xún)的查詢(xún)精度比較。由于Nettrace數(shù)據(jù)規(guī)模較小，因此將滑動(dòng)窗口的長(zhǎng)度設(shè)為數(shù)據(jù)集的大小，而在WorldCup98數(shù)據(jù)集中，為了便于比較，將滑動(dòng)窗口的大小設(shè)為65 536。

本節(jié)實(shí)驗(yàn)在每一時(shí)刻生成一次滑動(dòng)窗口內(nèi)的任意大小的隨機(jī)區(qū)間查詢(xún)，對(duì)比分析平均查詢(xún)誤差。實(shí)驗(yàn)對(duì)比結(jié)果如圖8、圖9所示。

Fig.6 Comparison of query efficiency under different query times(WorldCup98)圖6 每時(shí)刻不同查詢(xún)次數(shù)下的查詢(xún)效率比較（WorldCup98）

Fig.7 Comparison of query efficiency under different sizes of sliding window(WorldCup98)圖7 不同滑動(dòng)窗口大小下的查詢(xún)效率對(duì)比（WorldCup98）

Fig.8 Comparison of query accuracy under arbitrary size of query(Nettrace)圖8 任意查詢(xún)區(qū)間下的查詢(xún)精度對(duì)比（Nettrace）

Fig.9 Comparison of query accuracy under arbitrary size of query(WorldCup98)圖9 任意查詢(xún)區(qū)間下的查詢(xún)精度對(duì)比（WorldCup98）

從圖8、圖9可以看出，相比于RTP，RTP_MM具有更高的數(shù)據(jù)查詢(xún)精度,這是由于對(duì)滑動(dòng)窗口內(nèi)的樹(shù)結(jié)構(gòu)利用對(duì)角矩陣進(jìn)行了優(yōu)化,可在不改變時(shí)間效率的前提下進(jìn)一步提高查詢(xún)精度,而相比于FDA，在大數(shù)據(jù)集中RTP_MM由于使用了滑動(dòng)窗口從而使得樹(shù)高降低，敏感度下降而使得查詢(xún)精度提高，在小數(shù)據(jù)集中由于滑動(dòng)窗口與數(shù)據(jù)集大小一致，因此無(wú)差異。與HQ_DPSAP相比較精度誤差沒(méi)有明顯差異。而與原始的LP方法相比較，其他算法的誤差均低于LP方法。

結(jié)合查詢(xún)效率對(duì)比結(jié)果容易看出，RTP_MM算法可在顯著提高查詢(xún)效率的同時(shí)具有較優(yōu)的查詢(xún)精度。

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

本文針對(duì)差分隱私流數(shù)據(jù)實(shí)時(shí)發(fā)布問(wèn)題，提出了一種有效的實(shí)時(shí)發(fā)布方法，可針對(duì)滑動(dòng)窗口內(nèi)任意區(qū)間查詢(xún)提供時(shí)間復(fù)雜度為O(1)的查詢(xún)效率，同時(shí)保證較優(yōu)的查詢(xún)精度。本文主要針對(duì)數(shù)據(jù)發(fā)布的前置處理環(huán)節(jié)開(kāi)展研究工作，下一步將在數(shù)據(jù)發(fā)布的后置處理階段進(jìn)一步提升流數(shù)據(jù)發(fā)布方法的精度及性能。