随着信息技术的迅猛发展，现如今正面临着越来越多基于云原生数据库的实时数据流分析应用场景^[1-2]. 例如，在网络流量分析领域，云原生数据库可以存储和处理大量用户浏览行为数据流，以支持网站工作人员进行实时分析和商品推荐^[3-5]. 在车辆交通监测领域，云原生数据库能够存储车辆位置和移动数据流，并为实时交通信息系统提供支持，从而帮助优化交通流量和路线规划^[6-8]. 在金融交易监控领域，云原生数据库能够处理大量的交易数据流，支持实时监测和风险管理决策^[9-11].

在这些云原生数据库的应用场景中，快速生成和发布基于最新数据的直方图信息，以反映数据流中的最近群体趋势是至关重要的. 这是因为随着数据处理量的激增和实时性的不断提高，当前的应用程序更加注重最近的数据而非历史数据，因为最近的数据更有价值，更能反映当前数据的变化趋势. 例如，苹果公司在其云数据库中仅保留最近3个月的用户数据，超过此时间范围的数据往往被视为过时，从推荐的角度来看，任何超过3个月的数据都可能被认为是过时的^[12-13]. 进一步而言，数据流在线直方图发布算法作为云原生数据库的关键组成部分，对实现数据流分析的实时性和准确性至关重要. 因此，研究和优化这些算法不仅能够提升云原生数据库的性能和效率，还将直接影响到实际应用的数据分析能力和决策结果.

本文研究致力于解决一个具有挑战性的问题：如何在不断涌入新数据的无限数据流中快速而安全地生成数据直方图并进行发布. 具体而言，本文关注于在任意给定一个滑动窗口大小$w$和一个隐私预算$\varepsilon$（隐私保护强度参数）的情况下，如何实时生成并发布差分隐私直方图的问题. 该问题的关键要求是，需要在每个时刻都能够快速生成一个实时的差分隐私直方图，同时确保该直方图既可以有效地反映当前滑动窗口（数据流中最新的$w$条数据）内数据的群体趋势信息，又可以保护这$w$条数据中每个用户的隐私信息. 本文以数据流中每个时刻的滑动窗口快速生成差分隐私直方图为研究目标有2个原因：首先，差分隐私是针对最严格的攻击者模型而建立的隐私保护技术之一，具有广泛的应用前景，尤其是在云原生数据库等领域^[1-2,14-17]；其次，差分隐私建立在严格的数学理论基础上，并允许用户根据实际的应用场景设置合适的量化隐私保护强度^[18-23]. 此外，本研究对于云原生数据库中的数据流处理具有重要的意义. 在云环境下，对数据流进行实时分析和处理是至关重要的，而保护用户隐私则是不可或缺的要求. 因此，解决在不断涌入的数据流中实时生成差分隐私直方图的问题，将为云原生数据库等领域的数据管理和隐私保护提供有力的技术支持^[1-2,14-23].

目前，对于差分隐私直方图发布算法，无论是在静态数据还是动态数据方面，都有大量关于数据发布的研究工作^[24-35]. 然而，现有文献中提出的方法并未充分适用于数据流场景和滑动窗口模型. 注意：一般来说，对于数据流场景，人们一般要求所设计的算法具有在线性，即算法需要较低的时间和空间开销^[36-37]；对于滑动窗口模型，人们只关心数据流中最近的$w$条数据.

具体来说，这些已有的算法在发布数据流滑动窗口差分隐私直方图时，存在3个主要缺点：

1）对窗口内最近元素的关注不足. 最近元素是指在数据流处理中，滑动窗口内最近$w$条数据. 现有的直方图发布方法主要关注整体数据的统计特性，而不是特别关注滑动窗口内最近$w$的数据，且未考虑到数据流的特性，缺乏专门用于快速统计数据流滑动窗口中直方图的方法.

2）数据实时缓存需求导致高存储开销. 现有数据流直方图发布方法通常需要实时缓存整个窗口中的所有数据，即每个时刻都需要完整存储当前的最近$w$条数据. 这种存储方式导致较高的存储开销，并且缺乏对噪音的有效量化.

3）直接统计和对数据加噪带来的高时间开销. 现有的直方图发布方法直接对当前窗口内的全部数据进行统计，以生成准确的直方图，随后通过添加噪音的方式生成可发布的直方图. 然而，这种方法在每次生成可发布的直方图时都需要扫描当前窗口内的所有数据，因而带来相对较高的时间开销.

针对上述问题，提出了一种基于采样的数据流差分隐私快速发布算法（sampling based fast publishing algorithm with differential privacy for data stream，SPF）， 以实现对滑动窗口数据的高效发布，并在保障隐私的同时降低时间和空间开销，如图1所示. 该算法巧妙地将实时发布算法与滑动窗口采样相结合，使其适用于数据流的直方图数据发布. 通过设计一种新颖的内存高效的数据结构——高效数据流采样草图结构（efficient data stream sampling sketch structure，EDS），并利用数据流滑动窗口采样机制与差分隐私保护机制之间的内在关系，实现了自适应的加噪，生成符合隐私保护要求的直方图.

图  1  基于采样的数据流差分隐私快速发布算法

Figure  1.  Sampling based fast publishing algorithm with differential privacy for data stream

下载: 全尺寸图片 幻灯片

本文的主要贡献包括3个方面：

1）新颖的内存高效的数据流采样草图结构. SPF算法采用了滑动窗口模型来获取当前数据流中最新的数据，并提出了一种高效数据流采样草图结构EDS. 该结构在每个时刻对当前滑动窗口内的数据进行采样统计估计，通过非负约束过滤掉不符合要求的估计数据，从而实现对数据流中最近元素（每个时刻滑动窗口中的$w$条数据）的关键直方图信息的高效提取. 该草图结构可以提供完全符合差分隐私定义的噪声值，即证明了EDS输出的近似值从理论上等效于真实值加上一个满足$(\varepsilon ,\delta )$-差分隐私的噪声值. 该草图结构适用于滑动窗口模型连续发布直方图，并能够在使用较低的空间开销的情况下估计当前滑动窗口的统计计数值，并提供严格可控的数据保护能力.

2）基于高效的数据流采样的自适应加噪算法. EDS 算法的输出值是加噪后的近似值，尽管该值在一定程度上反映了原始数据流的真实情况，但仍可能暴露部分敏感信息. 为了解决这个问题，提出了一种基于高效数据流采样草图结构的自适应加噪算法. 该算法根据隐私保护强度与用户需求的隐私保护强度之间的差异来自适应添加噪音，满足了用户所需的隐私保护强度. 该算法提高了差分隐私直方图生成速度，并保证了相同的隐私保护强度.

3）隐私性和时空复杂度分析. 本文首先对SPF算法的隐私性进行了理论分析，使其满足差分隐私定义. 然后，对SPF算法的时间和空间复杂度进行了理论分析，以全面了解其性能. 最后，通过在真实数据集的实验分析，结果表明SPF算法可以使用较少的内存开销来快速实时生成直方图数据，同时发布的数据仍然提供了相同的可用性.

1.   相关工作

目前现有的基于差分隐私的直方图发布方法可以分为2类：1）静态数据的直方图发布方法；2）动态数据的直方图发布方法.

1.1   静态数据的直方图发布方法

最近的许多工作都致力于静态数据的直方图发布方法^[24-27]. 静态数据的直方图发布方法是基于一个固定的数据集进行分析和发布的. 这意味着数据在发布之前已经全部收集完毕，不再发生变化. Xu等人^[20]提出了SF（structure first）算法，其核心思想在于通过启发式压缩相似频率的间隔，以减少查询误差. 经过理论分析和实验证明，这一方法取得了良好的效果. Zhang等人^[25]提出了一种聚类方案AHP （accurate histogram publication），该方案可以均衡聚类引起的近似误差和拉普拉斯噪声注入引起的拉普拉斯误差，提高直方图发布的准确性. 张啸剑等人^[26]提出了一种精确的直方图发布算法DiffHR（differentially private histogram release），使用Metropolis-Hasting算法并联合指数排序方法对直方图中的每个区间数据进行排序，然后根据贪心聚类的思想对排序数据进行分组，提高直方图数据的可用性. 唐海霞等人^[27]提出了隐私预算自适应分配方法APB （adaptive privacy budget），通过优化隐私预算权重分配模型，计算出使得总误差最小的隐私预算权重分配比例，并通过贪心思想进行分组，均衡噪声误差和重构误差，提高数据的可用性.

1.2   动态数据的直方图发布方法

最近的一些研究工作提出了动态数据的直方图发布方法^[28-35]. 动态数据直方图发布是针对不断更新的数据流进行的，这意味着数据是实时获取和处理的. 林富鹏等人^[28]提出了一种定长二维数据流滑动窗口差分隐私统计发布算法PTDSS-SW，针对二维空间数据流，以较低空间开销实现隐私保护. 张啸剑等人^[29]提出了SHP（streaming histogram publication method with differential privacy），将滑动窗口中的桶计数分组，并根据数据采样结果自适应分配隐私参数，降低整体的隐私预算. Sun等人^[30]将Fenwick树和矩阵优化结合在一起，提出了一种完整的差分私有实时流数据发布算法RTP_DMM，在保证查询质量的同时有效提高了查询效率. Wu等人^[31]提出了一种以Kullback-Leibler散度为测度的直方图发布算法HPSSGC（histogram publishing algorithm based on sampling sorting and greedy clustering）. 该算法使用KL散度计算相邻数据之间的变化量，并在发布的数据中加入不同的噪声值，以减少基于KL散度计算的不同值的噪声误差. Cao等人^[34]提出了一种元算法，该算法可以使用现有的一次性Top-k方法作为DP算法子程序，从流中连续释放私有直方图. 2023年，Lebeda等人^[35]提出了一种基于经典Misra Gries草图结构的在线数据发布方法MGP^[38,39]，有效地平衡了数据的隐私性和实用性. 分析和实验结果证实，与以前的直方图发布方法相比，该方法可以提高处理效率和数据效用.

综上所述，不论是针对静态数据还是动态数据，现有的数据发布算法在处理数据流滑动窗口模型时都面临3个问题：

1）现有的动态数据直方图在实时数据流环境中具有潜在的应用价值，但其在数据处理延迟和空间消耗方面的挑战限制了其实际应用；

2）现有的数据流算法在数据发布过程中，未能充分考虑利用差分隐私和滑动窗口采样之间的数据内在相关性；

3）现有的数据流直方图发布算法在加噪过程中仅直接对统计数据添加噪音，未能充分满足用户对隐私保护强度的要求.

本文针对现有工作存在的问题，提出了一种基于差分隐私的数据流采样发布快速生成算法（SPF），如图1所示. SPF算法首先提出了内存高效的数据流采样草图结构，它能够对当前滑动窗口内的数据在每个时间戳进行采样估计，并且该草图结构能够提供严格可控程度的数据保护能力. 然后，本文提出了一种基于高效数据流采样的自适应加噪算法，该算法提高了直方图生成的速度，减少了运行时间，并提供了满足用户所需要的隐私保护强度.

2.   定义与模型

在本节中，主要介绍数据流差分隐私相关的定义与模型. 在表1中总结了本文所有常用的符号.

表  1  常用符号

Table  1.  Commonly Used Symbols

符号	描述
${{{e}}_{{t}}}$	在数据流${{DS}}$中当前时间点${{t}}$的元素
${{W}}$	滑动窗口
${{w}}$	滑动窗口的大小
${{{S}}^ + }$	采样中间集合
${{{s}}^ + }$	采样中间集合大小
${{S}}$	采样集合
${{s}}$	采样集合的大小
${{b}}$	随机性增强因子
${{r}}$	随机因子
${{l}}$	直方图区间个数
$\varepsilon$	隐私预算
$\beta$	隐私预算分配比例

下载: 导出CSV 

| 显示表格

2.1   数据流和滑动窗口模型

数据流被定义为一个可数无限的元素序列，并能够用于表示随时间推移可用的数据元素. 数据流被广泛应用于众多数据处理应用中，包括环境监测应用中的传感器读数、金融应用中的股票报价或计算机监测中的网络数据等.

定义1. 数据流. 给定一个无限数据流集${{DS = }}\{ {e_1}, {e_2},… ,{e_{{t}}},… \} (t \geqslant 0)$表示某个时间到达系统时所对应的元素.

滑动窗口模型是指在每一时刻处理最近的滑动窗口内的数据，并对该窗口内的所有数据进行统计计数处理. 滑动窗口模型能够很好地处理历史数据和近期数据. 滑动窗口模型定义如定义2所示.

定义2. 滑动窗口模型. 给定一个无限数据流集${{DS = }}\{ {e_1},{e_2},… ,{e_{{t}}},… \} (t \geqslant 0)$，滑动窗口大小$w$，当前时间戳$t$的滑动窗口包含$[t - w,t]$之间的$w$个元素.

2.2   差分隐私

如果一个机制的结果不受单个用户的删除或添加的显著影响，那么该机制就是差分隐私的. 因此，攻击者无法获取任何用户的信息，而不管该用户在原始数据库中是否存在.

定义3. 相邻的数据流. 给定2个数据流$D$和$D'$，如果$D$和$D'$之间最多有1个不同的元素，则表示$D$和$D'$是相邻的数据流.

定义4. 全局敏感度. 对于任意函数$f$，定义函数$f$的全局敏感度为：

定义5. $(\varepsilon ,\delta )$-差分隐私. 给定2个相邻的数据流$D$和$D'$，当且仅当对任意输出集$O \subseteq R ange(A)$存在以下不等式时，算法${G}$达到差分隐私保护要求.

其中，Range表示算法${G}$的可能输出的集合，$\varepsilon$表示隐私预算，$\delta$表示松弛项. 请注意，概率Pr来自于算法${G}$的内部随机性. 显然，隐私保护强度随着隐私预算$\varepsilon$的增加而增加.

定义6. 高斯噪声机制. 高斯噪声机制是从高斯分布中提取的噪声，其方差根据敏感度和隐私参数进行校准. 对于任意$\delta \in(0,1)$，$\varepsilon \in(0,1)$，其机制定义为：

其中，$u=0$，$\sigma^{2}=\dfrac{2{\rm in}\left(\dfrac{1.25}{\delta }(\Delta f)^2\right)}{\varepsilon^{2}}$. 高斯噪声机制提供$(\varepsilon ,\delta )$-差分隐私.

定义7. 差分隐私串行组合性质. 令${M_i}$提供${\varepsilon _i}$-差分隐私. ${M_i}({{D}})$的序列提供$\Big(\displaystyle\sum_{{i}} {{\varepsilon _i}} \Big)$-差分隐私，其中${M_i}$表示一个满足${\varepsilon _i}$-差分隐私算法，而${M_i}({{D}})$表示所有的算法作用于同一个数据集${{D}}$，那么这些算法构成的集合满足$\Big(\displaystyle\sum_{{i}} {{\varepsilon _i}} \Big)$-差分隐私.

3.   基于差分隐私的数据流采样发布快速生成算法（SPF）

3.1   高效数据流采样草图结构

SPF算法采用了滑动窗口模型来获取当前数据流中最新的数据，并提出了一种高效数据流采样草图结构（EDS），如算法1所示. 为了更好地描述相关算法，现对相关定义进行阐述.

1）采样中间集合. 实时数据流中通过滑动窗口模型的这些数据中随机抽取的采样集合大小为${{{s}}^ + }$的数据集合.

2）采样集合. 从采样中间集合中随机抽取的采样集合大小为${{s}}$的数据集合，用于近似代表整个数据流的特征.

3）过期数据. 不再处于当前滑动窗口内的数据，这些数据在新的窗口内不再具有代表性，应被移除或忽略.

算法1. EDS.

输入：时间$t$，滑动窗口大小${{w}}$，采样中间集合${{{S}}^{{ + }}}$，采样集合${{S}}$，采样中间集合大小${{{s}}^ + }$，采样集合大小${{s}}$，随机性增强因子${{b}}$；

输出：在每一个时刻的采样集合${{S}}$的元素.

① 初始化${{w}}$，${{{S}}^{{ + }}}$，${{S}}$，${{{s}}^ + }$，${{s}}$，${{b}}$；

② for $t \in [1,{s^ + }]$ do

③　${S^ + _1}(t) = t,\;\;{S^ + _2}(t) = {e_t}$；

④　for $t \in (1,s)$ do

⑤　　将${S^ + }$中的数据赋值给$S$中的数据；

⑥　end for

⑦　for $t \in (s,{s^ + })$ do

⑧　　${r_1} = randi([1,t])$；

⑨　　if ${r_1} < {s^ + }$ then

⑩　　　${r_2} = randi([1,{s^ + }])$；

⑪　　　${S^ + _1}({r_2}) = t,\;\;{S^ + _2}({r_2}) = {e_t}$；

⑫　　end if

⑬　 $S$=Delete(${S^ + }$，${\text{max}}(0,{s^ + } - s)$)；

⑭　end for

⑮ end for

⑯ for $t \in ({s^ + },w)$ do

⑰　${r_1} = randi([1,t])$；

⑱　if ${r_1} \lt {s^ + }$ then

⑲　　${r_2} = randi([1,{s^ + }])$；

⑳　　${S^ + _1}({r_2}) = t,\;\;{S^ + _2}({r_2}) = {e_t}$；

㉑　end if

㉒　$S$=Delete(${S^ + }$，${s^ + } - s = b$)；

㉓ end for

㉔ for $t > w$ do

㉕　${r_1} = randi([1,t])$；

㉖　if ${r_1} < {s^ + }$ then

㉗　　${r_2} = randi([1,{s^ + }])$；

㉘　　${S^ + _1}({r_2}) = t,\;\;{S^ + _2}({r_2}) = {e_t}$；

㉙　end if

㉚　$S$=Delete(${S^ + }$，${s^ + } - s = b$)；

㉛ end for

算法1的具体步骤如下所示：

1）对于当前时刻t$\in [1,{s^ + }]$内，把每一个时刻的时间戳和计数值都记录下来. 其中当前时刻t$\in [1,s]$，采样集合的数据与采样中间集合的数据一致；当前时刻t$\in [{{s}},{s^{{ + }}}]$，从采样中间集合${{{S}}^{{ + }}}$中随机删除${{t - s}}$个元素作为采样集合（行②~⑭）.

2）对于当前时刻t$\in [{s^ + }{{,w}}]$，首先检查采样中间集合中是否有过期数据，如果存在过期元素，则加入最新的数据，如果没有过期元素，则以随机的概率$\dfrac{{s + b}}{t}$进行替换. 然后，从采样中间集合${{{S}}^{{ + }}}$中随机删除${{b}}$个元素作为采样集合（行⑮~㉑）.

3）对于当前时刻$t > {{w}}$，首先检查采样中间集合中是否有过期数据，如果存在过期元素，则加入最新的数据（即当前采样集合中有随机的概率$\dfrac{{s + b}}{w}$的过期元素） ¹；如果没有过期元素，则以随机的概率$\dfrac{{s + b}}{w}$进行替换. 然后，从采样中间集合${{{S}}^{{ + }}}$中随机删除${{b}}$个元素作为采样集合（行㉒~㉘）.

高效数据流采样草图结构能够在每个时间戳对当前滑动窗口内的数据进行采样统计估计，实现了对数据流中关键直方图信息的高效提取. 该草图结构可以提供完全符合差分隐私定义的噪声值——证明了EDS结构输出的近似值从理论上等效于真实值加上一个满足$(\varepsilon ,\delta )$-差分隐私的噪声值. 该草图结构适用于滑动窗口模型连续发布直方图，并能够在使用较低的空间开销时估计当前滑动窗口的计数值. 该EDS结构提供严格可控程度的数据保护能力.

3.2   基于高效数据流采样的自适应加噪算法

本文提出了一种基于高效数据流采样的自适应加噪算法，如算法2所示.

算法2. 基于高效数据流采样的自适应加噪算法.

输入：时间$t$，滑动窗口大小${{w}}$，采样集合$S$，采样集合大小${{s}}$，隐私预算分配比例$\beta$，EDS采样集对应的区间计数${\eta _{{i}}}$，隐私预算$\varepsilon$；

输出：发布噪音直方图${\bar {{H}} _{{W_{{t}}}}}$.

① 分配隐私预算：${\varepsilon }_{1}\text{=}\beta \varepsilon ，{\varepsilon }_{2}\text{=}(1{-}\beta )\varepsilon$；

② 计算区间的阈值误差：$error_{\min}=\dfrac{2\rm{l}\mathrm{n}(1.25/\delta)}{\varepsilon_1^2}+$ $\dfrac{2\mathrm{\rm{l}n}(1.25/\delta)}{\varepsilon_2^2}$；

③ 计算隐私预算分配参数$\beta$；

④ 采样集合区间计数：$\{ {\eta _1},{\eta _2},… ,{\eta _{{l}}}\}$；

⑤ 计算当前时间$t$的滑动窗口区间计数：${{{H}}_{{W_{{t}}}}} =$ $\{ {\eta _1},{\eta _2},… ,{\eta _{{l}}}\} \times \dfrac{w}{{{s}}}$；

⑥ 发布噪音直方图： ${\bar {{H}} _{{W_{{t}}}}} = {H_{\text{W}}}_{_{{t}}}{{ + }}{Gaussian} \left(\dfrac{{\Delta f}}{{{\varepsilon _2}}}\right)$.

算法2的具体步骤如下所示：

1）分配2段隐私预算的比例（行①）.

2）根据基于分组的高斯噪声来计算差分隐私分配参数$\beta$（行②~③）.

3）根据高效数据流采样的计算结果，计算区间结果（行④~⑤）.

4）添加第2部分噪声值（行⑥).

基于高效数据流采样的自适应加噪算法通过衡量隐私保护强度与用户需求的隐私保护强度之间差异来自适应添加噪声，满足用户所需的隐私保护强度. 该算法在提高数据流差分隐私直方图生成速度的同时，保证了满足用户要求隐私预算下的相似的隐私保护强度.

4.   理论分析

4.1   EDS算法的理论基础

本节中，我们深入探讨了EDS结构的理论基础，特别是关注了该算法中若干关键引理和定理的作用与意义.

EDS算法的理论基础主要围绕EDS结构的均匀性证明（定理1）展开，这些理论构件为SPF算法的设计逻辑、操作流程以及性能分析提供了坚实的数学保障.

引理1. 在任一时刻${{t}}$，采样集合${S^ + }$中的数据为EDS结构从当前滑动窗口中均匀随机选取的$|{s^ + }|$条数据.

证明.

1）当${{t}} \in [1,{{s + }}b]$时，引理1显然成立，即在${{t}} \in [1, {{s + }}b]$时，$Pr ({{{S}}^ + } = \{ {e_1},{e_2},… ,{e_t}\} ) = 1$；

2）当${{t}} \in [s + b + 1,w]$时，对于${{t}} = s + b + 1$来说，基于算法1可知${{{e}}_{s + b + 1}}$将以$\dfrac{{s + b}}{{{{s}} + b + 1}}$的概率替换原来的采样中间集合${{{S}}^ + }$中的一条记录，从而在${{t}} = s + b + 1$的时刻可知：

由此，对于元素${{{e}}_{s + b + 1}}$来说，它替换采样集合${{{S}}^ + }$中的记录的概率为$\dfrac{1}{{{{s}} + b + 1}}$，并且${{{e}}_{s + b + 1}}$没有替换的概率：$Pr ({{{S}}^ + } = \{ {e_1},{e_2},… ,{e_t}\} ) = \dfrac{{s + b}}{{s + b + 1}}$，从而${{t}} = s + b + 1$时，引理1也成立.

3）利用相似的分析方法可得，当${{t \gt w}}$时，引理1成立.

根据以上3点分析，可以知道在任一时刻${{t}}$，采样集合${S^ + }$中的数据为从当前滑动窗口中均匀随机选取的$|{s^ + }|$条数据，所以引理1成立. 证毕.

定理1. 在任一时刻${{t}}$来说，令$W$为滑动窗口，$w$为滑动窗口大小，则$S$等于$W$的任何一个$S$-子集的概率等于$\dfrac{1}{{C_s^w}}$.

证明. 对于任一时刻${{t}}$，对于$W$来说分成2种情况：

1）$W = \{ {e_1},{e_2},… ,{e_t}\} ,{\text{ }}(t < w)$

对于当前时刻$t \lt w$来说，可以知道当前滑动窗口中的元素为$W = \{ {e_1},{e_2},… ,{e_t}\}$. 由引理1可知，采样集合${S^ + }$中的${s^ + }$条数据是从$W$中随机选取的${s^ + }$条数据. 由此，可知采样集合概率满足：

另外，由于算法1将${S^ + }$中的${s^ + } - s$条数据随机删除. 由此，由算法1可知采样集合概率满足：

2）$W = \{ {e_{t - w + 1}},{e_{t - w + 2}},… ,{e_t}\} ,{\text{ }}(t \geqslant w)$

对于当前时刻$t \geqslant w$来说，可以知道当前滑动窗口中的元素为$W = \{ {e_{t - w + 1}},{e_{t - w + 2}},… ,{e_t}\}$. 同样，由引理1可知，采样集合${S^ + }$中的${s^ + } = s + b$条数据是从$W$中随机选取的$s + b$条数据，从而

$Pr ({S^ + } = {\text{Any (}}s + b) -{\rm subset}\;{\rm in} \; W) = \dfrac{1}{{C_{{s^ + }}^w}}$.

另外，由算法1随机删除采样集合${S^ + }$中$b$条数据来生成采样集合$S$. 由此，知道采样集合概率：

根据情况1和情况2所满足的采样集合概率，即式（3）（4）可以知道定理1成立.

在所设计的数据结构EDS中，实际上使用了采样集合s中的区间个数$\hat \eta$，并使用$\hat \eta$来估计真实计数值$\eta$，其中$\hat \eta \times \dfrac{w}{s}$表示真实计数值$\eta$的估计结果. 证毕.

定理2. 数据结构EDS中的$E\left(\hat \eta \times \dfrac{w}{s}\right)$$= \eta$.

证明. 对于数据结构EDS来说，可知$E(\hat \eta ) = \dfrac{{s\eta }}{w}$. 根据引理1可知数据结构EDS对于每个数据点被选择的概率是相等的. 因此其估计通常是无偏估计的. 可知$E\left(\hat \eta \times \dfrac{w}{s}\right) = \dfrac{{s\eta }}{w} \times \dfrac{w}{s} = \eta$. 所以数据结构EDS中的$E\left(\hat \eta \times \dfrac{w}{s}\right)=$$\eta$. 证毕.

定理3. 通过数据结构EDS所生成的采样计数值与当前窗口内的真实计数值之间的方差为

证明. 对于任何给定的区间间隔$I$来说，当前滑动窗口中的$w$个元素可以表示为二进制位字符串. 那么可以说明当${e_i} \in {I_i}$，则对应的位为1，否则为0，判断该元素是否满足当前区间.

在不失一般性的情况下，假设对于某个直方图间隔$I$，当前滑动窗口中属于当前区间的数量为$\eta$，不属于当前区间的数量为$w - \eta$，其中$\eta$表示当前滑动窗口中的真实计数值.

$\hat \eta$满足分布：

其中，$m$表示当前滑动窗口内区间的估计计数结果，$w$表示滑动窗口大小，$s$表示采样集合$S$的长度.

为了证明数据结构EDS所生成的采样计数值与当前窗口内的真实计数值之间的方差，公式推导过程如下所示：

首先，$\eta$的方差$D(\eta ) =$0，这是因为当滑动窗口大小给定时，$\eta$是一个常数值，而不是一个随机变量.

根据式（6），可以得到$D\left(\hat \eta \times \dfrac{w}{s} - \eta \right) = \dfrac{{\eta (w - \eta )}}{{w - 1}}\dfrac{{w - s}}{s}$. 当滑动窗口大小给定时，式（6）中的$\dfrac{{\eta (w - \eta )}}{{w - 1}}$是一个常数值. 证毕.

为了确定方程的单调性，现在只需要确定$\dfrac{{w - s}}{s}$函数的单调性，因此对$f(s) = \dfrac{{w - s}}{s}$进行求导运算：

因为式（7）结果小于0，可知式（6）随着采样集合的变大而方差逐渐减小. 当滑动窗口大小$w$等于采样集合$S$的长度$s$时，说明对滑动窗口内所有数据都进行了采集，估计值与真实值相同，所以数据结构EDS的方差为0.

令$\hat \eta$表示属于某个区间${{I}}$的数据个数，数据结构EDS从最近的${{w}}$个元素中随机选取${{s}}$个元素并统计满足当前区间的个数，下面证明$\hat \eta$近似服从正态分布.

引理2. $\hat \eta$近似服从正态分布${{N}}\left(\dfrac{{s\eta }}{w},\dfrac{{s\eta }}{w}\Bigg(1 - \dfrac{\eta }{w}\Bigg)\cdot \dfrac{{w - s}}{{w - 1}}\right)$，其中$\eta$表示当前窗口中属于区间${{I}}$的计数个数，${{s}}$表示采样集合的大小，${{w}}$为滑动窗口大小.

证明. 对于区间${{I}}$，当前滑动窗口中的${{w}}$个元素可以转化为${{w}}$个数，其中0表示对应的数据不属于${{I}}$，1表示对应的数据属于${{I}}$；由于数据结构EDS是从${{w}}$个元素中均匀选择${{s}}$个元素，因此从式（1）可知$\hat \eta$等于m的概率.

由于数据流上的滑动窗口大小${{w}}$一般会设置一个较大的值，这是因为对于一个较小的${{w}}$，内存可以有条件地保存所有的窗口记录，因此不需要进行特殊的内存设计，以实现高效的数据流算法^[18,19].

根据正态分布可得到方程：

根据式（5）（8）显然可知：数据结构EDS中的$\hat \eta$近似服从正态分布${{N}}\left(\dfrac{{s\eta }}{w},\dfrac{{s\eta }}{w}\left(1 - \dfrac{\eta }{w}\right)\dfrac{{w - s}}{{w - 1}}\right)$. 证毕.

定理4. 数据结构EDS近似服从正态分布${{N}}\left(0,\dfrac{{{{{w}}^2}}}{{{{{s}}^2}}}\dfrac{{s\eta }}{w}\left(1 - \dfrac{\eta }{w}\right)\dfrac{{w - s}}{{w - 1}}\right)$.

证明. 根据引理2可知，$\hat \eta$近似服从正态分布${{N}}\left(\dfrac{{s\eta }}{w},\dfrac{{s\eta }}{w}\left(1 - \dfrac{\eta }{w}\right)\dfrac{{w - s}}{{w - 1}}\right)$. 那么，$\left(\dfrac{{{w}}}{{{s}}}\hat \eta {-\text{ }}\eta \right)$近似服从正态分布${{N}}\left(0,\dfrac{{{{{w}}^2}}}{{{{{s}}^2}}}\dfrac{{s\eta }}{w}\left(1 - \dfrac{\eta }{w}\right)\dfrac{{w - s}}{{w - 1}}\right)$，数据结构EDS近似服从正态分布${{N}}\left(0,\dfrac{{{{{w}}^2}}}{{{{{s}}^2}}}\dfrac{{s\eta }}{w}\left(1 - \dfrac{\eta }{w}\right)\dfrac{{w - s}}{{w - 1}}\right)$. 证毕.

4.2   SPF算法的隐私性

定理5. SPF算法满足$(\varepsilon ,\delta )$-差分隐私定义.

证明. SPF算法主要是由2部分组成：高效数据流采样草图结构和基于高效数据流采样的自适应加噪算法. 这2部分都需要满足差分隐私算法.

1）情况1. 采样集合大小小于等于采样集合最大大小时.

① 高效数据流采样草图结构

EDS直接反映出滑动窗口内数据结果，采样集合实际上是包含了窗口内的真实数据，则EDS对应的隐私预算${\varepsilon _1} = 0$，不需要添加高斯噪声.

② 基于高效数据流采样的自适应加噪算法

基于高效数据流采样的自适应加噪算法，会根据当前隐私预算${\varepsilon _2} = \varepsilon$直接添加相应的高斯噪声.

根据定义7，该隐私预算将满足所有区间的隐私保护要求，那么SPF算法满足$(0 + \varepsilon ,\delta )$-差分隐私，即SPF算法满足$(\varepsilon ,\delta )$-差分隐私定义.

2）情况2. 采样集合大小大于采样集合最大值时.

① 高效数据流采样草图结构

根据定理4可知，给定一个滑动窗口大小${{w}}$和一个采样集合${{s}}$，EDS的$\left(\dfrac{{{w}}}{{{s}}}\hat \eta {-\text{ }}\eta \right)$近似服从正态分布${{N}}\left(0,\dfrac{{{{{w}}^2}}}{{{{{s}}^2}}}\dfrac{{s\eta }}{w}\left(1 - \dfrac{\eta }{w}\right)\dfrac{{w - s}}{{w - 1}}\right)$. 加入的高斯噪声的标准差$\sigma$通常是$\sigma=\Delta f\dfrac{\sqrt{2\mathrm{\rm{l}n}(1.25/\delta)}}{\varepsilon_1}$计算得到. 给定高斯噪声的标准差$\sigma$，正态分布$N(\mu ,{\sigma ^2})$表示为$N\left(0,\dfrac{2\rm{ln}(1.25/\delta)}{\varepsilon_1^2}\right)$.

根据高斯分布所产生的误差与EDS所产生的误差相等，得到：

其中，${\varepsilon _1}$的取值主要由窗口大小w和采样集合大小s决定.

由此，草图结构等价于每个区间都分配与隐私预算为${\varepsilon _1}$相同的高斯噪声所量化的噪声.

② 基于高效数据流采样的自适应加噪算法

该算法通过动态调整噪声值，使滑动窗口采样的估计误差与差分隐私噪声值之和能够满足用户的差分隐私需求. 具体来说，算法会根据数据流的特点和用户设定的隐私参数，精确地控制噪声的添加量.

由此，基于高效数据流采样的自适应加噪算法等价于在每个时间区间内分配与隐私预算为${\varepsilon _2}$相同的高斯噪声.

根据定义7，该隐私预算将满足所有区间的隐私保护要求，那么SPF算法满足$({\varepsilon _1} + {\varepsilon _2},\delta )$-差分隐私，即SPF算法满足$(\varepsilon ,\delta )$-差分隐私定义.

根据情况1和情况2，SPF算法满足$(\varepsilon ,\delta )$-差分隐私定义. 证毕.

4.3   SPF算法的空间代价和时间代价

本节对SPF算法的时间和空间代价进行了深入的分析.

定理6. 基于差分隐私的数据流采样发布快速生成算法SPF的空间复杂度为${{O}}({{s}})$.

证明. SPF 算法由2个主要部分组成：高效数据流采样草图结构EDS和基于高效数据流采样的自适应加噪算法. 这2个算法分别实现了对滑动窗口数据的快速采集和隐私保护.

1） 高效数据流采样草图结构EDS

EDS 用于对滑动窗口数据进行快速采集，提取关键特征. 这一过程中，EDS 会构建一个包含所有可能的采样中间集合${{{s}}^ + }$.

采样集合${{s}}$是从采样中间集合中选取的子集，因此 EDS 的空间开销主要由中间集合${{{s}}^ + }$的大小决定.

2）基于高效数据流采样的自适应加噪算法

该算法根据隐私预算比率分配比例来进行加噪，从而保证数据发布的差分隐私特性. 这一步并不会显著增加空间开销，因为加噪是基于采样集合${{s}}$进行的.

综上所述，通过详细分析 EDS 和基于高效数据流采样的自适应加噪算法的空间开销，可以得出SPF算法的空间复杂度为${{O}}({{s}})$. 证毕.

计算SPF算法的时间代价，首先我们需要计算EDS所需要的时间开销，然后计算SPF算法的时间开销.

定理7. EDS消耗的时间复杂度为${{O}}({{s}})$.

证明. EDS的时间复杂度主要由时间戳和计数值记录的操作、过期数据的检查和删除操作，以及随机的样本替换操作组成. 为了证明 EDS 的时间复杂度，需要详细分析其每一步的操作及其对应的时间消耗.

1）时间戳和计数值记录的操作. 每一个时刻只有1个数据进入${{O}}(1)$.

2）过期数据的检查和删除操作. 样本集合中最多纪录$s + b$条数据记录，并且这种操作最多需要遍历这$s + b$条记录1次${{O}}({{s}})(s \gg b)$.

3 随机的样本替换操作. 不存在过期数据，直接随机替换${{O}}(1)$；

将上述3个步骤的时间复杂度综合考虑，EDS 的时间复杂度为${{O}}({{s}})$ . 证毕.

定理8. 已知采样中间集合的大小为${{s}} + b$，则SPF算法消耗的时间开销为${{O}}({{s}})$.

证明. 对于任意的滑动窗口，SPF 算法的处理过程主要分为2个部分：

1）高效数据流采样算法EDS. 构建一个包含所有可能采样数据的中间集合，这一步的时间复杂度为${{O}}({{s}})$，由定理7可知.

2）基于高效数据流采样的自适应加噪算法. 基于采样集合进行加噪，加噪过程的时间开销通常较小.

通过对这2个部分的分析，时间开销最主要的主体在于通过高效数据流采样草图结构EDS获得采样集合时所需要的处理时间. 因此，对于SPF算法的时间复杂度为${{O}}({{s}})$. 证毕.

5.   实验分析

5.1   实验设置

本实验的硬件环境为Inter Core i7-13700KF 8-core3.4 GHz，16 G RAM，1 TB硬盘内存存储，软件环境为Windows 11操作系统，MatlabR2021b编程语言.

本文使用了在差分隐私中广泛使用的数据集^[21,23]Taxi和Traffic进行实验.

1）Taxi数据集是一个黄色的出租车旅行记录数据集，包括捕获接送日期/时间、司机报告的乘客数量等，由纽约市出租车和豪华轿车委员会网站提供，选择了2019年1月至2019年12月的纽约市黄色出租车出行数据集作为实验数据集.

2）Traffic数据集是一个详细的道路安全数据集，关于人身伤害的情况、道路事故由英国警方提供，他们收集每一辆汽车碰撞的数据. 选取了从2005—2014年的伤亡者档案中包含年龄、性别等信息的数据集作为实验数据集.

对于这2个真实数据集，使用了MatlabR2021b编程语言实现SPF算法、HPSSGC算法^[31]、MetaAlgo算法 ^[33]和MGP算法^[35]. 所有算法的算法复杂度对比如表2所示 ². 将本文SPF算法与其他3种算法进行了实验比较，并对实验结果进行了验证.

表  2  算法复杂度对比

Table  2.  Comparison of Algorithm Complexity

算法	时间复杂度	空间复杂度
HPSSGC	${{O}}(w\log w)$	$O(w)$
MetaAlgo	${{O}}(w + l)$	$O\left(\dfrac{1}{\varepsilon }\log \dfrac{1}{\delta } + w\right)$
MGP	${{O}}(w)$	$O\left(\dfrac{1}{\varepsilon } + w\right)$
SPF（本文）	${{O}}({{s}})$	$O({{s}})$

下载: 导出CSV 

| 显示表格

5.2   性能评估标准

本实验主要比较了平均内存使用量、平均运行时间和数据的准确性. 平均内存使用量是滑动窗口发布一个直方图所需要的内存空间. 平均运行时间是运行算法程序在每一时刻发布数据流数据的直方图所需的平均时间. 数据的准确性是采用均方根误差（root mean square error，RMSE）来评价数据的精度.

RMSE的计算公式为

其中，${{i}}$表示第${{i}}$个区间，${{{H}}_{{i}}}$表示第${{i}}$个区间间隔查询所对应的真实计数值，${\bar {{H}} _{{i}}}$表示当前区间间隔发布的噪声值.

5.3   SPF算法的隐私预算分配设置

为了测试SPF算法中隐私预算在不同的分配比例下对可用性产生怎样的影响. 对于2种不同数据集，固定滑动窗口和分块的大小，将$\beta$设置范围为(0, 1). 将采用式（1）（2）计算总误差.

对于某一个区间计算来说，总误差的构成为：

1）在高效数据流采样算法中，该算法等效于差分隐私中隐私预算为${\varepsilon _1}$的噪声；

2）在基于高效数据流采样草图结构的自适应加噪算法中，在该算法中使用了隐私预算为${\varepsilon _2}$的噪声.

总误差的计算公式为：

为了满足数据的可用性，对于总误差来说，需要使总误差取最小值，即考察下面的最小化问题：

需要将${\varepsilon }_{1}\text{=}\beta \varepsilon ，{\varepsilon }_{2}\text{=}(1{-}\beta )\varepsilon$带入${{error} _{\min }}$获得式（13）.

为了取当前总误差的最小值（达到最好的数据可用性），只需要取式（13）的$\dfrac{1}{{{\beta ^2}}}{{ + }}\dfrac{1}{{{{(1 - \beta )}^2}}}$的最小值即可. 式（13）可以获得式（14）.

首先，需要对式（14）进行求导，求导结果如式（15）所示.

然后，令${{f'}}({{x}})=0$，即$- \dfrac{2}{{{x^3}}} + \dfrac{2}{{{{(1 - x)}^3}}}=0$，可得

解得式（16）的结果为$x=0.5$. 为了验证$x=0.5$是最小值，$f(x)$的二阶导数当$x=0.5$结果为$192>0$.给定函数$f(x)$可以在$x=0.5$获得最小值. 所以，最后对应的结果为${{x = }}0.5$.

当隐私预算比例$\beta$在0.1~0.5之间时，随着隐私预算比例$\beta$的增加，${\varepsilon _1}$增加，${\varepsilon _2}$减少，对于总误差来说，总误差在慢慢减少；当隐私预算比例$\beta$在0.5~1之间时，随着隐私预算比例$\beta$的继续增加，${\varepsilon _1}$减少，${\varepsilon _2}$增加，对于总误差来说，总误差在慢慢增加. 因此，在后面的实验中，SPF算法中的隐私预算分配比例$\beta=0.5$.

5.4   实验结果分析

本文分析了在2种不同的真实数据集下的算法性能.

5.4.1   不同滑动窗口下的算法性能

对于4种算法，改变滑动窗口大小w，并在$\varepsilon$=0.1的条件下测量平均运行时间、平均内存使用量和RMSE，结果如图2、图3所示.

图  2  不同滑动窗口大小的Taxi数据集上的性能

Figure  2.  Performance on Taxi dataset with different sliding window sizes

下载: 全尺寸图片 幻灯片

图  3  不同滑动窗口大小的Traffic数据集上的性能

Figure  3.  Performance on Traffic dataset with different sliding window sizes

下载: 全尺寸图片 幻灯片

在图3中，当w = 30000时，SPF的平均运行时间，平均内存使用和RMSE分别为$2.55 \times {10^{{-\text{ }}4}}$ s，$4.5 \times {10^4}$ bit，108. 相比之下，HPSSGC，MetaAlgo和MGP需要的平均运行时间分别为$2.72 \times {10^{{-\text{ }}3}}$ s，$1.65 \times {10^{ - 3}}$ s，$1.2 \times {10^{{-\text{ }}3}}$ s；HPSSGC，MetaAlgo和MGP需要的平均内存使用量分别为$2.37 \times {10^5}$ bit，$1.5 \times {10^5}$ bit，$1.2 \times {10^5}$ bit；HPSSGC， MetaAlgo和MGP需要的RMSE分别为189， 108， 108.

从图2和图3中可以得出2点结论：

1） 即使在滑动窗口大小w较小时，SPF 依然比HPSSGC，MetaAlgo和MGP 展现出更快的运行时间和更低的内存使用量. 这一观察结果突显了滑动窗口估计计数草图和基于 EDS 的自适应直方图生成算法的固有效率. 随着滑动窗口的变化，需要采集的样本集合大小会增大，因为为了保证相同的数据精准度，必须采集更多的样本以保持一致.

2）随着滑动窗口大小w的增加，所有方法的误差保持不变. 出现这种现象的原因是，在固定的隐私预算情况下，这些方法利用统计数据并随后引入噪声，导致误差水平持续存在. 隐私预算决定了数据流的差分隐私保护程度，而滑动窗口大小的调整对数据效用的影响可以忽略不计.

总之，与其他算法相比，所提出的SPF在不同滑动窗口中平均运行时间显著降低了63%，平均内存使用量显著降低了50%.

5.4.2   不同隐私预算下的算法性能

在不同隐私预算$\varepsilon$下评估了4种算法在2个真实数据集上的性能，如图4和图5所示. 固定了w = 50000，隐私预算设置$\varepsilon$从 0.02 ~0.1 不等.

图  4  不同隐私预算的Taxi数据集上的性能

Figure  4.  Performance on Taxi dataset with different privacy budgets

下载: 全尺寸图片 幻灯片

图  5  不同隐私预算的Traffic数据集上的性能

Figure  5.  Performance on Traffic dataset with different privacy budgets

下载: 全尺寸图片 幻灯片

图5中，当$\varepsilon =0.06$时，SPF的平均运行时间、平均内存使用量和RMSE分别为$2.23 \times {10^{{-\text{ }}4}}$ s， $5.75 \times {10^4}$ b，181. 相比之下，HPSSGC，MetaAlgo和MGP需要的平均运行时间分别为$2.2 \times {10^{{-\text{ }}3}}$ s，$1.2 \times {10^{ - 3}}$ s，$1.4 \times {10^{{-\text{ }}3}}$ s；HPSSGC，MetaAlgo和MGP需要的平均内存使用量分别为$3.95 \times {10^5}$ b，$2.5 \times {10^5}$ b，$2 \times {10^5}$ b；HPSSGC，MetaAlgo和MGP需要的RMSE分别为 290，181，181.

从图4和图5中可以得出3点结论：

1）更大的隐私预算会导致SPF算法的运行时间和内存使用量的增加. 这种现象与滑动窗口估计计数草图和基于EDS的自适应直方图生成算法的理论有效性一致. 随着隐私预算的增大，需要采集的样本集合也会变大，因为隐私预算越大，数据值越准确，因此需要采集的数据更多. 这意味着，随着隐私预算的增加，算法需要处理更多的数据和计算，从而增加了资源消耗.

2）随着隐私预算的增加，RMSE会降低，表明数据效用更高，但隐私保护水平降低. 这一观察结果与实用性和隐私性之间的权衡模式一致. 也就是说，在较高隐私预算下，尽管数据的准确性提高，但泄露敏感信息的风险也相应增加.

3）最重要的是，SPF在运行时间和内存使用量方面始终优于其他方法，同时保持相似的数据效用. 这显示了SPF算法在实际应用中的高效性和竞争力，使其成为在资源受限环境中进行数据分析的优选方案.

总之，与其他算法相比，在不同的隐私预算下，SPF算法平均运行时间显著减少了65%，平均内存使用量显著减少了69%.

6.   总结与展望

本文的研究提出了一种基于差分隐私的数据流采样发布快速生成算法SPF，旨在实现差分隐私下的实时数据流发布. 该算法包含2个关键创新点：高效数据流采样算法和基于高效数据流采样的自适应加噪算法. 首先，为了降低时间和空间开销，提出一种新颖的内存高效的数据流采样草图结构. 该数据结构可以快速对数据流进行统计，从而更快地获取统计值，并且可以满足量化的差分隐私，保证$(\varepsilon ,\delta )$-差分隐私条件，提供严格可控的数据保护能力. 然后，为了满足用户所提供的隐私保护强度，并且避免正确反映原始数据流的真实情况，提出一种基于高效数据流采样的自适应加噪算法. 该算法通过对高效数据流采样算法的误差和差分隐私误差进行量化，并在数据发布过程中添加差分隐私噪声，以达到用户所需的隐私保护强度. 在2个真实数据集上进行了实验验证，结果表明SPF算法能够快速处理数据流，并根据用户要求自适应地添加噪声，以发布满足差分隐私保护要求的直方图数据.

SPF算法对于滑动窗口差分隐私直方图的快速发布很有用，但仍存在一些局限性. 遵循先前的工作假设每个区间结果具有相同的可靠性程度. 然而，在实际情况中，不同区间的结果可能具有不同的隐私属性. 因此，未来将计划扩展SPF算法提供个性化差分隐私的机制.

作者贡献声明：王修君提出并设计了算法方案和实验方案，并进行论文修改；莫磊完成实验部分并撰写论文；郑啸、卫琳娜、董俊、刘志检验算法的性能，提出指导意见，并参与论文修改；郭龙坤把握论文的总体创新性，验证理论分析和实验分析的正确性，并负责论文的最终修订.