差分隱私流數據實時發布方法*

葛 晨，吳英杰，孫 嵐

福州大學 數學與計算機科學學院，福州 350116

1 引言

當前，許多應用受益于流數據的連續統計監測，如基于位置的服務通過實時的統計信息向用戶推薦商店，社交網絡通過實時地統計用戶來獲得熱門話題，這些應用均需用到流數據的實時統計值。然而，這類數據的發布在為用戶帶來便利的同時，還可能伴隨著泄露用戶敏感隱私信息的風險[1]。

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

本文的主要貢獻如下：

（1）針對流數據應用中存在需要大量實時查詢的情形，提出一種支持高效查詢的流數據實時發布方法。

（2）利用矩陣在處理關聯性查詢方面的優勢，在查詢效率量級不變的前提下利用對角矩陣優化進一步提高發布方法的查詢精度。

（3）通過仿真實驗，驗證本文方法的有效性與可行性。

2 基礎知識與相關定義

2.1 差分隱私定義

Dwork等人首次提出了差分隱私模型[2]，該模型是一種強健的隱私保護框架，通過減少修改數據集中一條記錄對查詢結果的影響，使得攻擊者即使知道了除某條記錄外的所有記錄信息，也無法準確獲得該條記錄中的敏感信息。

定義1（兄弟數據集）給定數據集D、D′，當兩個數據集之間只相差一條記錄時，即：

則稱D、D′為兄弟數據集，其中表示數據集中記錄的數量。

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

則稱算法A滿足ε-差分隱私。

定義3（敏感度）對某數據庫中的數據集D和D′分別進行統計，得到兩組由列向量表示的統計結果：。那么查詢集Q的敏感度ΔQ定義如下：

其中，xi表示查詢的結果。

2.2 差分隱私流數據區間計數查詢

定義4（流數據）流數據是一組順序、大量、快速、連續到達的數據序列。一般情況下，流數據可被視為一個隨時間延續而無限增長的動態數據集合。

利用區間樹可以有效提高數據的發布精度，但是在流數據的背景中隨著數據的逐漸增加，會使得隱私預算耗盡而降低數據的隱私保護程度。Chan等人[7]根據實際應用背景，利用滑動窗口機制來發布流數據，避免了隱私預算耗盡的問題。

定義5（滑動窗口下的流數據區間計數查詢）設當前數據序列的時序為t，數據序列為S={C1,C2,…,Ct}，用戶提出的查詢操作為q，查詢操作定義為在滑動窗口內的某段連續統計計數值的累加和查詢，查詢操作q的查詢范圍為[lq,rq](t-W＜lq≤rq≤t)，而相應的查詢結果可由如下公式表示：

滑動窗口下的流數據發布如圖1所示。

Fig.1 Streaming data in sliding window圖1 滑動窗口下的流數據發布

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

3 滑動窗口下的差分隱私流數據實時發布

本章主要介紹基于滑動窗口的樹結構模型構建，給出復雜度為O(n)的實時發布方法，同時在此框架下利用矩陣機制提高發布數據的查詢精度而不降低查詢效率。

3.1 模型構建

利用區間樹構建差分隱私發布模型，可以提高數據發布的效率，從而適應流數據的實效性要求。在文獻[7]中，其通過完全二叉樹的結構來組織表示與發布數據，其具體表示形式如圖2所示。

Fig.2 Construction process of interval tree in sliding window圖2 滑動窗口下的區間樹構建過程

設滑動窗口大小為|W|，當前時刻為t。如圖2中所示，滑動窗口內各包含兩棵二叉樹的一部分。其中，灰色節點已滑出滑動窗口，在之后查詢發布中不再涉及這些節點，而條紋節點為即將使用的節點，在樹中第一個節點進入滑動窗口時整棵二叉樹中的所有節點已經預先建立，隨著逐步進入滑動窗口，這些節點將相應地被激活。

在完全二叉樹的構建方法中，對于單次查詢而言，其查詢時間復雜度為O(lbn)，與樹的高度相關，當滑動窗口大小較大且每一個時刻需求大量查詢時，其耗時較多。可以通過對頻繁查詢的區間進行存儲，但是其提升效率的同時將造成大量的內存開銷。本文將通過去除完全二叉樹中的部分節點，實現連續統計發布，并通過連續統計的發布值得到滑動窗口內任意區間查詢的計數值，使其單次查詢的時間復雜度降為O(1)。其表示如圖3所示。

通過圖3中的二叉樹結果，可以提供樹中任意區間的查詢計數值。但是對于連續統計而言，樹中的虛線節點是不必要的，樹中每個右子節點的信息將保存在其父節點中。假設滑動窗口的大小為W，則樹中需要保存的節點也為W，因此根據樹中的節點關系，可以在O(1)時間內計算出當前連續統計過程中涉及的最新節點。

Fig.3 Dynamic construction process of interval tree in sliding window圖3 滑動窗口中的區間樹動態構建過程

樹狀數組是一個對于查詢和修改的時間復雜度均為O(lbN)的數據結構，對于給定的r，可以快速求得區間[1,r]的和值。設區間[1,r]的和為Sum(r)，即。

樹狀數組在計算過程中，生成了中間統計量Si(i∈[1,r])，如下：

其中，Dj表示第j個數的值,lowbit(x)將x表示二進制后，只保留其最低位的1的對應值。以x=12為例，(12)10=(1100)2，最低位的1為右數第三位，則lowbit(x)=(0100)2=(4)10。通過補碼性質可知，lowbit(x)=x&(-x)。而后，樹狀數組通過中間統計量Si，得到區間和值如下：

按照時序對當前時刻涉及的節點進行編號，可將圖3中的實線節點表示為樹狀數組，如圖4所示，其中①～④為一棵樹，⑤～⑦為另一棵樹，樹的大小不應超過滑動窗口大小以導致存儲冗余節點。實節點左邊的數字為其節點編號，其中節點①的值為t1時刻的統計值，節點②為t1與t2時刻的統計值的和，節點③的值為t3時刻的統計值，節點④為t1～t4時刻的統計值的和值。由于父節點表示為其所有子節點的累加和值（對于給定的x，如果x+lowbit(x)等于y，則把編號為x的節點稱為y的子節點，編號為y的節點稱為x對應的父節點），每個節點其對應的父節點是唯一的，因此每個節點只會參與一次累加過程，即對于節點④而言，其值為節點②的值、節點③的值與t4時刻的實際統計值之和，同時節點②與節點③的值只會在節點④的計算過程中使用到，可以在計算節點②時，為節點④預先開辟空間，與此同時將節點②的值累加到節點④上，而節點⑤～⑦在另一棵樹中，其計算過程與節點①～③的計算過程相同，因此在建樹過程中，時間復雜度是線性的。

Fig.4 Construction process of tree array圖4 樹狀數組建樹過程

連續統計發布過程中可使用如圖4所示的樹結構，區間[1，1]的值為節點①的值，區間[1，2]的值為節點②的值，區間[1，3]的值為節點②與節點③的和，區間[1，5]的值由于橫跨兩棵樹，其值為節點④與節點⑤的和值，其余節點與上述節點計算過程相同。考慮在同一棵樹中的發布過程中，對于時刻t7而言，將7表示為二進制111，則時刻t7的發布值為節點⑦的值、節點⑥的值與節點④的值的和，而時刻t6的發布值為節點⑥的值與節點④的值的和，因此t7時刻的發布值可以表示為時刻t6的發布值與節點⑦的值的和。因此對于單次查詢而言，其時間復雜度為O(1)。

Fig.5 Insert node and create new tree圖5 節點插入，建立新樹

滑動窗口在移動過程中如圖5所示，首先根據預先設置的滑動窗口大小，選擇合適的樹高，使得樹的大小不會超出滑動窗口大小。圖5中滑動窗口大小為5，因此可以預先定義樹高為3。在圖5中，移出滑動窗口的過期節點將不再使用而被回收，減少存儲開銷。同時在完成一棵樹之后，新到達的節點會根據設置好的樹高，構建一棵新的待完成的樹。

對于給定的滑動窗口大小W，其樹高也為之確定，假設其為H，根據式（3）可得其敏感度為H，因此對于樹中的每一個節點添加噪聲規模為H的Laplace噪聲[12]，可以使得算法滿足ε-差分隱私。

具體算法過程如下：

算法1節點插入算法Insert

算法2滑動窗口下的任意區間查詢實時發布算法RTP

3.2 利用矩陣機制優化查詢精度

由于在連續統計發布過程中無法實現任意區間的查詢，因此需要通過連續統計的發布值來獲得。例如，在圖4中，區間[2，5]的和需要通過[1，4]+[4，5]-[1，2]的值來得到，因此會涉及到已發布結果中的多個統計值，造成噪聲的累加，使得查詢精度下降。但是，連續統計發布過程設定了特殊的查詢區間[1，t]，因此可以通過查詢和查詢間的關聯性來降低誤差，并且不降低其查詢效率。

樹狀數組生成中間變量的過程可以通過矩陣與向量相乘的形式表示，當r=7時，其表示形式如下：

其中，L表示策略矩陣，D表示原始數據集，S表示中間變量向量，即通過策略矩陣將數據表示為中間變量的形式，添加噪聲后再利用矩陣將其還原為查詢結果。式（7）表示將原始發布值轉換為圖3中樹結構中實節點的過程。

同時，當樹結構確定后，即可通過式（6）將其還原成為需要的連續統計發布值，當r=7時，用矩陣表示其形式如下：

其中，W表示查詢的負載矩陣。在連續統計發布背景中，其形式如下：

即連續統計發布結果可以表示為WD=BLD，且W=BL。

在將樹結構轉換為矩陣形式后，本文方法可以作為矩陣機制的一種特殊分解策略。矩陣機制是通過將負載矩陣W進行矩陣分解，得到一種最優的分解策略，以提高數據的發布精度。本文則是設計一種特殊形式的矩陣分解策略，誤差高于矩陣機制中的最優分解策略，但是其可以通過樹狀數組的方式快速求解，從而滿足流數據的實時性要求。根據文獻[13]的結論，其均方誤差為：

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

同時，轉換為矩陣機制后，本文將通過文獻[14]的結論，提高其發布精度。根據其結論，存在一個對角矩陣Λ，從而使得W=BL?W=BΛΛ-1L，通過選取合適的對角矩陣，可以提高數據的發布精度。

其相應的均方誤差變為：

通過調整對角矩陣可以使得誤差進一步降低，文獻[14]給出具體求解方法，其過程如算法3所示。

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

其中，ΔL表示矩陣L的敏感度；表示根據給定的噪聲規模產生每一維均是獨立Laplace噪聲的向量。

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

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

將樹結構表示為矩陣后，結合對角矩陣系數優化方法，形成算法RTP_MM，其算法過程如下：

算法3對角陣系數求解算法getLamta

算法4節點插入算法Insert 2

算法5基于快速對角矩陣的滑動窗口下的任意區間查詢實時發布算法RTP_MM

4 實驗分析

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

4.1 實驗數據與環境

為方便對比與分析，本文采用了文獻[15]中的數據集NetTrace，以及文獻[16]中使用的WorldCup98數據集進行對比實驗。NetTrace數據集包含了某單位在特定時間段內對特定IP段的數據包請求次數。WorldCup98為1998年4月至1998年7月期間，世界杯官網的訪問量的統計記錄。其數據規模如表1所示。

在實驗中，采用均方誤差衡量算法發布數據的查詢精度，誤差公式如下：

Table 1 Data set表1 數據集

其中，|Q|為查詢的數量；D為原始數據集；D′為添加噪聲后的發布結果；q表示一次查詢。

實驗環境為：Intel Core i5 4570 3.2 GHz處理器，8 GB內存，Windows 7操作系統；算法用C++語言實現；由Excel生成實驗圖表。

4.2 查詢效率的對比分析

（1）查詢次數對查詢效率的影響

本節實驗在每時刻設置不同的查詢次數來比較4種算法的查詢效率，由于在小數據集上查詢效率變化不明顯，因此實驗只使用WorldCup98數據集來考察查詢效率，其中查詢區間大小均設為32 768，涉及滑動窗口的算法其窗口大小固定為65 536，實驗結果如圖6所示。

從圖6可以看出，除了HQ_DPSAP外，利用連續統計發布而獲得滑動窗口內任意區間查詢值的算法的查詢效率基本一致。只有在查詢次數較少時有所差異，這是因為在查詢次數較少時，影響查詢效率的主要因素是模型構建所花費的時間，RTP與RTP_MM算法在模型構建上的時間復雜度均為O(N)，因此在圖6中兩條曲線基本重合，而FDA算法的模型構建時間復雜度[14]為O(NlbN)，因此其查詢效率要略低些；當查詢次數增加時，占效率主導地位的是查詢時所花費的時間，且隨查詢次數的增加而增加。利用連續統計發布結果來獲得任意區間查詢結果的算法的查詢效率為O(1)，而HQ_DPSAP通過構建區間樹來實現滑動窗口內任意區間查詢，雖可使查詢所涉及的樹中節點個數較少，但由于每次查詢均要重新遍歷樹高，因此對于單次查詢而言，其時間復雜度為O(lbW)，與其滑動窗口大小相關，故查詢效率較低。

（2）滑動窗口大小對查詢效率的影響

本節實驗設置不同的滑動窗口大小來比較4種算法的查詢效率，由于在小數據集上查詢效率變換不明顯，因此實驗只使用WorldCup98數據集來考察查詢效率，滑動窗口大小分別設置為215,216,…,221，查詢區間大小設為滑動窗口大小的一半，以使得查詢區間大小隨滑動窗口增加而增加，查詢次數設為每時刻查詢一次。實驗結果如圖7所示。

從圖7可以看出，隨著滑動窗口大小的增加，RTP、FDA算法的影響最小，滑動窗口只影響RTP算法的空間大小，而對于FDA算法而言，查詢效率只與流數據的預設大小相關，與滑動窗口大小無關。對于RTP_MM算法而言，滑動窗口會影響其預處理的時間，而與查詢無關，而HQ_DPSAP算法的查詢效率是O(lbW)，因此隨著滑動窗口大小的增加，其查詢時間會逐步增加，因此RTP、FDA、RTP_MM算法均位于其下方。

4.3 查詢精度的對比分析

實驗將在Nettrace、WorldCup98兩個數據集上進行滑動窗口下的任意區間查詢的查詢精度比較。由于Nettrace數據規模較小，因此將滑動窗口的長度設為數據集的大小，而在WorldCup98數據集中，為了便于比較，將滑動窗口的大小設為65 536。

本節實驗在每一時刻生成一次滑動窗口內的任意大小的隨機區間查詢，對比分析平均查詢誤差。實驗對比結果如圖8、圖9所示。

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

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

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

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

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

結合查詢效率對比結果容易看出，RTP_MM算法可在顯著提高查詢效率的同時具有較優的查詢精度。

5 結束語

本文針對差分隱私流數據實時發布問題，提出了一種有效的實時發布方法，可針對滑動窗口內任意區間查詢提供時間復雜度為O(1)的查詢效率，同時保證較優的查詢精度。本文主要針對數據發布的前置處理環節開展研究工作，下一步將在數據發布的后置處理階段進一步提升流數據發布方法的精度及性能。