实际应用场景中，人们常常关注特定数据在某个时间段的统计结果，如医疗记录中近一周的就诊量、交易数据中某季度的成交量。这些统计结果均以流数据在某种意义下的实时计数值为科学依据。然而，流数据发布不可避免地存在用户隐私泄露风险^[1]。针对差分隐私流数据统计发布问题, 文[2]提出一种二进制数据流下的持续性计数查询方法；文[3]采用二叉树实现对无限长度数据流连续发布的隐私保护；文[4]在滑动窗口下统计分析特定流数据查询子集，回答特定用户批次查询；文[5]提出滑动窗口内多种权重衰减下的差分隐私流数据统计发布方法；文[6]基于滑动窗口分割的流式直方图实现对流数据的差分隐私保护；文[7]实现滑动窗口下对多事件流数据的隐私预算分配与差分隐私保护；文[8]采用滑动窗口机制对多条流数据进行重要流检测，保证近期数据的发布精度，避免了噪声累加和隐私预算耗尽问题；文[9]借助Kalman滤波器和差分隐私理论处理流数据，提高数据可用性；文[10]改进了加噪及直方图重组方法，实现差分隐私流数据发布中区间查询、滑动窗口及事件监测的同步处理。

以上研究工作从不同方面解决了流数据发布中隐私保护的相关问题，但大多采用同方差加噪方式，且未考虑加噪数据是否满足一致性约束，所发布流数据的查询精度仍存在较大的提升空间。为此，本文拟采用滑动窗口机制，动态建立滑动窗口内流数据的差分隐私区间树，结合历史查询的统计结果对滑动窗口内区间树进行异方差加噪和树结构调整，并对加噪后的区间树进行实时的一致性约束优化，以实现对发布流数据查询精度的提升。

1 基础知识与问题描述 1.1 差分隐私

定义1  ε-差分隐私：给定兄弟数据表^[11]T₁、T₂，若随机发布算法A对该兄弟数据表的所有可能输出O⊆range(A)均满足

$ \Pr \left[ {A\left( {{T_1}} \right) \in O} \right] \le {{\rm{e}}^\varepsilon } \times \Pr \left[ {A\left( {{T_2}} \right) \in O} \right]. $

(1)

则称算法A满足ε-差分隐私^[11]。其中：range(A)表示算法A的取值范围，A(T)表示以T作为算法A的输入时得到的输出，Pr[A(T)∈O]表示输出A(T)∈O的概率。

1.2 差分隐私流数据区间计数查询

定义2  区间计数查询：设当前时刻为t，流数据序列为S={C₁, C₂, …, C_t}，C_i为时刻i的统计计数值，用户查询q对应的查询区间表示为[l_q, r_q]，流数据区间计数查询的结果为

$ {\rm{result}} = \sum\limits_{i = {l_q}}^{{r_q}} {{C_i}} . $

(2)

对C_i进行加噪得到${{\tilde C}_i}$。随着时间的推移，在大范围的区间查询中，C_i与加噪值${{\tilde C}_i}$存在的噪声误差会导致噪声累加，进而使查询精度大幅下降。

为了有效提高查询精度和查询效率，已有研究采用差分隐私区间树对流数据进行构建，然而流数据序列无限增长将使差分隐私区间树的树高不断增大，节点不断增加，隐私预算不断分配，最终导致隐私预算耗尽，降低了隐私保护强度。为解决此问题，研究人员提出了基于滑动窗口的流数据发布方法^[5-8]。

滑动窗口下差分隐私区间树定义如下：

定义3  滑动窗口下的差分隐私区间树：给定流数据序列S={C₁, C₂, …, C_t}，滑动窗口W的大小为w，对滑动窗口内的流数据建立差分隐私区间树T如图 1所示。该区间树满足以下特性：

1) 每个树节点对应流数据序列中的区间[l_x, r_x]；

2) 区间树上节点x的隐私预算为ε_x，真实计数值为h_x，对该节点添加噪声后得到加噪计数值$\widetilde {{h_x}}$=h_x+Lap(1/ε_x)，则该节点满足ε_x-差分隐私。

2 异方差加噪下的差分隐私流数据发布

为了实现异方差加噪下的差分隐私流数据发布并提高查询精度，首先需要动态构建滑动窗口内的差分隐私区间树。

2.1 滑动窗口内动态构建差分隐私区间树

针对滑动窗口内区间树动态变化的特点，文[8]提出一种动态构建区间树的方法，但其构建的区间树为固定二叉树，致使针对所发布流数据的查询精度受到限制。本文引入分叉数k和树高h等构树参数，在进行隐私预算分配的过程中动态调整区间树结构，以适应不同查询规律的需要，可以进一步提高查询精度。如图 2所示。

2.2 异方差加噪

在差分隐私区间树中，不同节点被查询区间覆盖的概率通常不同。相比于同方差加噪，异方差加噪对覆盖概率高的节点添加较小噪声，而对覆盖概率低的节点添加较大噪声，可有效降低整体误差^[12]。

令p_x为区间树节点x的查询覆盖概率，QP(l, r)表示区间[l, r]被区间查询q覆盖的概率，f_x为x的父节点。由定义3可知，p_x满足：

$ {p_x} = \left\{ \begin{array}{l} QP\left( {{l_x}, {r_x}} \right), \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x = r;\\ QP\left( {{l_x}, {r_x}} \right) - QP\left( {{l_{{f_x}}}, {r_{{f_x}}}} \right), \;\;\;\;其他. \end{array} \right. $

(3)

设NodeSet(q)为查询q所覆盖的节点集合，则：

$ \begin{array}{*{20}{c}} {{\rm{NodeSet}}\left( q \right) = }\\ {\left\{ {x\left| {{l_q} \le {l_x} \wedge {r_x} \le {r_q} \wedge \neg \left( {{l_q} \le {l_{fx}} \wedge {r_{fx}} \le {r_q}} \right)} \right.} \right\}.} \end{array} $

(4)

对x添加Laplace噪声时，其误差期望为^[12]

$ {\rm{EErr}}\left( q \right) = \sum\limits_{x \in {\rm{NodeSet}}\left( q \right)} {\frac{2}{{\varepsilon _x^2}}} . $

(5)

设QC(x)为查询集合Q中节点x被覆盖的次数, QC(x)=p_x·|Q|。则整棵区间树的查询平均误差期望为

$ \begin{array}{*{20}{c}} {{\rm{EErr}}\left( Q \right) = \frac{{\sum\limits_{q \in Q} {\sum\limits_{x \in {\rm{NodeSet}}\left( q \right)} {\frac{2}{{\varepsilon _x^2}}} } }}{{\left| Q \right|}} = }\\ {\frac{{\sum\limits_x {\left( {QC\left( x \right) \cdot \frac{2}{{\varepsilon _x^2}}} \right)} }}{{\left| Q \right|}} = \sum\limits_x {\frac{{2{p_x}}}{{\varepsilon _x^2}}} .} \end{array} $

(6)

设${\bar \varepsilon }$为所有树节点的隐私预算向量，Leaf(root)表示所有叶子节点集合，Path(x, root)表示节点x到根节点的路径上的节点集合，在ε-差分隐私下区间查询误差期望最小化问题可形式化为EErr(Q)

$ \begin{array}{*{20}{c}} {{\rm{Minimize}}\;f\left( {\bar \varepsilon } \right) = {\rm{EErr}}\left( Q \right) = \sum\limits_x {\frac{{2{p_x}}}{{\varepsilon _x^2}}} }\\ {{\rm{s}}.\;{\rm{t}}.\;\;\;\forall x \in {\rm{Leaf}}\left( {{\rm{root}}} \right), \sum\limits_{z \in {\rm{Path}}\left( {x, {\rm{root}}} \right)} {{\varepsilon _z} = \varepsilon } .} \end{array} $

(7)

令Son(x)表示节点x的所有子节点；fson(x)为节点x的左起第一个子节点；k_x表示节点x的加噪系数，简称节点系数。为得到式(7)所示最小化问题的最优解，差分隐私区间树的异方差加噪方案需满足：

$ \begin{array}{*{20}{c}} {{k_x} = \left\{ \begin{array}{l} 1, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x \in {\rm{Leaf}}\left( {{\rm{root}}} \right);\\ 1 - \frac{1}{{{{\left( {\frac{{{p_x}}}{{\sum\limits_{y \in {\rm{Son}}\left( x \right)} {\frac{{{p_y}}}{{k_y^3}}} }}} \right)}^{\frac{1}{3}}} + 1}}, \;\;\;\;其他. \end{array} \right.}\\ {{\varepsilon _x} = {k_x}{\rm{psum}}\left( x \right), }\\ {{\rm{psum}}\left( x \right) = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} {\varepsilon _x}, \\ {\rm{psum}}\left( {{\rm{fson}}\left( x \right)} \right) + {\varepsilon _x}, \end{array}&\begin{array}{l} x \in {\rm{Leaf}}\left( {{\rm{root}}} \right);\\ 其他. \end{array} \end{array}} \right.} \end{array} $

(8)

其中历史查询统计下的节点覆盖概率为

$ {p_x} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} {\rm{QSum}}\left( {{w_x}} \right), \\ {\rm{QSum}}\left( {{w_x}} \right), - {\rm{QSum}}\left( {{w_{fx}}} \right), \end{array}&\begin{array}{l} x = {\rm{root}};\\ 其他. \end{array} \end{array}} \right. $

(9)

其中：w_x表示节点x所统计区间的宽度，

$ {\rm{QSum}}\left( x \right) = \frac{{\sum\limits_{y \ge x} {\sum\limits_{z \ge y} {{\rm{QP}}\left( z \right)} } }}{{w - x + 1}}, $

QP(z)表示在历史查询中，长度为z的查询区间出现的概率。结合历史查询，计算节点覆盖概率，即可进一步调节隐私预算分配方案。如图 3所示。

在原构树参数的基础上，可根据查询区间覆盖概率，进行新构树参数生成及误差期望计算。若误差期望差值t′ < 0，则接受新构树参数。否则，根据Metropolis准则，以概率exp(-t′/T)接受新构树参数。

至此，结合所计算的隐私预算分配方案，即可进行滑动窗口下的异方差加噪及树结构动态构建，如图 4所示。

2.3 一致性约束优化

基于动态构建的差分隐私区间树，设计合理的异方差加噪和隐私预算分配方案并进行树结构调节，可有效提高区间计数查询的精度。然而，加噪前的区间树父节点的计数值等于其子节点的计数值之和；但加噪后对于相同的区间树，父节点的加噪计数值可能与其子节点的加噪计数值之和不相等。已有研究^[12]表明，异方差加噪后的区间树，可利用一致性约束，进一步提高发布数据的查询精度。

为了证明异方差加噪方式和一致性约束条件下，仍可采用最优线性无偏估计对区间树进行优化调整，首先给出以下2个结论。

结论1  在差分隐私区间树中，从叶节点z到根节点root路径上的节点集合，其线性无偏估计值h满足：

$ \sum\limits_{x \in {\rm{Path}}\left( {{\rm{root}}, z} \right)} {\varepsilon _x^2{{\bar h}_x}} = \sum\limits_{x \in {\rm{Path}}\left( {{\rm{root}}, z} \right)} {\varepsilon _x^2{{\tilde h}_x}} . $

(10)

其中：${{\tilde h}_x}$为节点x的加噪统计值，${{\bar h}_x}$为节点x的线性无偏估计值。

根据结论1求解最小二乘问题，得到以下结论。

结论2  以x为根的子树中，x的估计值${{\bar h}_x}$、叶节点到x的估计值加权和${{\bar g}_x}$，均是关于x的线性方程：

$ \begin{array}{*{20}{c}} {{{\bar g}_x} = \sum\limits_{y \in {\rm{Path}}\left( {x, {\rm{Bound}}\left( x \right)} \right)} {\varepsilon _y^2{{\bar h}_y}} = {\alpha _x}{{\bar h}_{{\rm{Bound}}\left( x \right)}} + {c_x}, }\\ {{{\bar h}_x} = \sum\limits_{y \in {\rm{Leaf}}\left( x \right)} {{{\bar h}_y}} = {\beta _x}{{\bar h}_{{\rm{Bound}}\left( x \right)}} + {d_x}, } \end{array} $

(11)

$ {\alpha _x} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} \varepsilon _x^2, \\ {\alpha _w} + \varepsilon _x^2{\beta _x}, \end{array}&\begin{array}{l} x \in {\rm{Leaf}}\left( {{\rm{root}}} \right);\\ 其他. \end{array} \end{array}} \right. $

(12)

$ {\beta _x} = \left\{ \begin{array}{l} 1, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x \in {\rm{Leaf}}\left( {{\rm{root}}} \right);\\ \sum\limits_{y \in {\rm{Son}}\left( x \right)} {\frac{{{\beta _y}{\alpha _w}}}{{{\alpha _y}}}} , \;\;\;\;\;其他. \end{array} \right. $

(13)

$ {c_x} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} 0, \\ {c_w} + \varepsilon _x^2{d_x}, \end{array}&\begin{array}{l} x \in {\rm{Leaf}}\left( {{\rm{root}}} \right);\\ 其他. \end{array} \end{array}} \right. $

(14)

$ {d_x} = \left\{ \begin{array}{l} 0, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x \in {\rm{Leaf}}\left( {{\rm{root}}} \right);\\ \sum\limits_{y \in {\rm{Son}}\left( x \right)} {\left( {\frac{{{\beta _y}}}{{{\alpha _y}}}\left( {\begin{array}{*{20}{c}} {{{\tilde g}_y} - {{\tilde g}_w} - }\\ {{c_y} + {c_w}} \end{array}} \right) + {d_y}} \right)} , \;\;\;\;其他. \end{array} \right. $

(15)

$ {{\tilde g}_y} = \sum\limits_{u \in {\rm{Path}}\left( {y, {\rm{Bound}}\left( y \right)} \right)} {\varepsilon _u^2{{\tilde h}_u}} . $

(16)

其中：Bound(x)是以x为根节点的子树中左起第一个叶节点；w为x的第一个子节点；α_x、β_x、c_x、d_x称作节点调节参数。

通过计算节点x的调节参数并利用式(11)即可计算节点x的线性无偏估计值，进而实现对加噪后的差分隐私区间树的优化调节。

在流数据发布背景下，树结构随时间推移动态变化。如图 5a所示，当新节点t+1移入滑动窗口时，需同时生成父节点M并计算其调节参数。

由于节点M进行了加噪，为满足一致性约束条件，需调整所有子节点的发布值。如图 5b所示，在查询时可通过树节点的层级标识layer，判断该层发布值是否为最新(图中为2)。若过期(小于2)，则根据节点参数重新计算，并更新层级标识。至此，可在动态构建区间树的同时，计算节点调节参数。如图 6所示。

2.4 基于滑动窗口的差分隐私流数据一致性优化算法

在计算节点调节参数后，可通过算法5，在计算节点发布值提供区间计数查询的同时，对一致性约束下进行调节优化的发布值进行实时更新。

综合算法3-5，形成基于滑动窗口的差分隐私流数据一致性优化算法CCDPSD，如图 8所示。

2.5 算法分析

结论3  算法CCDPSD满足ε-差分隐私。

证明  在算法CCDPSD中，由结论1可知，隐私预算分配与异方差加噪过程均满足ε-差分隐私。而在对加噪值进行一致性约束条件下的优化调节时，并未造成额外隐私泄露和隐私预算占用。由差分隐私并行组合特性^[13]可知，算法满足ε-差分隐私。

结论4  算法CCDPSD为线性时间复杂度。

证明  在CCDPSD算法中，对移入滑动窗口的新节点计算加噪值、调节参数与层级标识的复杂度为O(1)。设滑动窗口大小为w，一次区间计数查询操作的复杂度为O(logw)。过期发布值均在查询过程中更新，复杂度同样为O(logw)。由于w规模有限，logw近似为常数，从而，查询的均摊复杂度接近于O(1)。设数据流长度为n，查询次数为m，CCDPSD算法的时间复杂度为O(n+m)，为线性复杂度。

3 实验结果与分析 3.1 实验环境

采用3个数据集进行实验，数据规模如表 1。

实验采用平均方差作为误差衡量的标准：

$ {\rm{Error}}\left( Q \right) = \frac{{\sum\limits_{q \in Q} {{{\left( {q\left( T \right) - q\left( {T'} \right)} \right)}^2}} }}{{\left| Q \right|}}. $

(17)

实验环境：Intel Core i7 930，4 GB，Windows 8.1；算法采用C++语言编程实现；由MATLAB生成实验图表。

3.2 查询精度

通过实验将一致性优化算法CCDPSD与Boost算法^[14]、LUE-DPTree算法^[15]及本文的DPSDHQ算法进行对比分析。由于Search Logs、Nettrace数据集规模小，所以实验中将CCDPSD算法的滑动窗口大小设置为数据集长度，以验证该算法对查询精度优化的有效性。并通过设置不同隐私参数、不同查询规律，验证CCDPSD算法对查询精度的优化效果。

3.2.1 不同区间大小下的查询误差对比

通过生成随机固定长度的查询区间，对比分析不同算法的区间查询误差。其中，区间大小分别取2⁰, 2¹，…，2¹²各随机生成10³条查询。对于Search Logs和Nettrace数据集，将算法CCDPSD与Boost算法、LUE-DPTree算法、DPSDHQ算法的查询误差进行对比，在对数坐标下，结果如图 9和10所示。

从图 9和10看出，CCDPSD算法误差最小；随着查询区间的增大，Boost、LUE-DPTree、CCDPSD算法的误差越来越接近；由于DPSDHQ算法未进行一致性优化，其查询误差较大。

由于数据集WorldCup98较大，不适合直接以数据集大小作为滑动窗口的大小，故采用1天中的秒数(86 400 s)作为滑动窗口大小。而Boost算法和LUE-DPTree算法并非基于滑动窗口，所以只将算法CCDPSD与算法DPSDHQ进行对比，采用对数坐标，结果如图 11所示。

从图 9-11的查询误差对比可以看出，本文的CCDPSD算法，在区间计数查询精度上优于Boost算法和LUE-DPTree算法，并能基于DPSDHQ算法进行有效的优化调节。

3.2.2 不同查询规律下的查询误差对比

设滑动窗口大小为w，通过对4种不同查询分布规律进行实验对比，分析算法CCDPSD对不同查询规律的适应性：Small，查询区间集中于1~0.33 w；Middle，查询区间集中于0.33 w~0.67 w；Large，查询区间集中于0.67 w~w；Rand，在滑动窗口范围内随机生成查询区间。实验中采用1.0作为隐私预算。实验结果如图 12-14所示。从图 12-14可以看出，相比于DPSDHQ算法，CCDPSD算法在不同查询规律下对误差精度均有明显提升。这是因为CCDPSD算法在一致性约束条件下进行了调节优化，降低了父节点与子节点计数值之和的差距，有效降低了区间计数的查询误差。

3.2.3 流数据动态发布过程中的查询误差对比

针对流数据的发布特性，在WorldCup98数据集下，随时间t的延续，对滑动窗口W进行区间计数查询，每10⁴ s记录整体误差，分析CCDPSD算法的一致性优化的效果。结果如图 15所示。

在图 15中，数据发布初期，树结构调整和历史查询统计尚不充足，DPSDHQ算法查询误差产生小幅波动，在后续中趋稳。而CCDPSD算法有效降低了初期的误差波动。同时在发布过程中由于CCDPSD算法进行了一致性调节优化，查询误差优于DPSDHQ算法。

综上，CCDPSD算法能适应流数据发布场景，有效降低区间计数查询误差。

3.3 算法运行效率

下面通过实验对算法运行效率进行对比分析：

3.3.1 不同隐私参数对运行效率的影响

设置不同的隐私参数(1.0、0.1、0.01)，对比分析算法运行效率与隐私参数的关系，如图 16所示。

从图 16可以看出，隐私参数的变化对算法的运行效率没有明显的影响。算法运行时间与隐私参数不相关。

3.3.2 一致性约束下优化过程对运行效率的影响

将算法DPSDHQ、CCDPSD进行效率对比。如图 17所示，CCDPSD算法具有与DPSDHQ算法相近的运行效率。正如结论4，由于采用了适应于流数据发布背景的算法设计流程，CCDPSD算法能够在实现在一致性约束条件下进行实时优化的同时，仍旧保持算法的线性时间复杂度。

综上实验对比与分析，本文提出的一致性优化算法CCDPSD具有较高的算法运行效率，在提高查询精度的同时，能够保证流数据发布背景下对算法复杂度的要求。

4 结论

本文针对滑动窗口下流数据发布问题，主要完成了以下工作：

1) 在滑动窗口下，动态构建差分隐私区间树；分析区间树节点的查询覆盖概率，并结合历史查询统计结果进行隐私预算分配和树结构调整，设计基于异方差加噪的差分隐私流数据发布算法。

2) 针对异方差加噪后区间树节点值可能不满足一致性约束的问题，设计实时的一致性调节策略，提出差分隐私流数据发布一致性优化算法。

本文的算法面向任意树结构，为区间查询精度的提升提供了更大的空间。通过理论分析，证明了本文的算法在满足差分隐私的前提下具有适用于流数据发布的算法复杂度。实验结果表明，本文算法具有较高的时间效率，能有效提升查询精度，具有较高的应用价值。