(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210804131.X (22)申请日 2022.07.07 (71)申请人 安徽工业大学 地址 243032 安徽省马鞍山市湖东中路59 号 申请人 合肥综合 性国家科 学中心人工智能 研究院 （安徽省人工智能实验室） (72)发明人 王修君　莫磊　郑啸　何诗兴　 (74)专利代理 机构 南京九致知识产权代理事务 所(普通合伙) 32307 专利代理师 王晓青 (51)Int.Cl. G06F 17/18(2006.01) G06F 21/62(2013.01) (54)发明名称 一种具有差分隐私的在线流式采样发布方 法及系统 (57)摘要 本发明提供一种具有差分隐私的在线流式 采样发布方法及系统， 涉及信息安全领域； 通过 一次扫描数据流， 将数据流中每个元素的属性统 计信息存储到一个具有高效处理能力的数据结 构SES中， 再根据该数据结构SES的采 集数据进行 直方图生 成和发布， 该发布数据与差分隐私算法 拥有相同的隐私保护强度保障； 其中， 数据结构 SES近似存储每个滑动窗口显著降低的存储成 本， 根据其采集数据能快速生成直方图， 减少数 据处理过程中的运行时间。 权利要求书3页 说明书10页 附图1页 CN 115114584 A 2022.09.27 CN 115114584 A 1.一种具有差分隐私的在线流式采样发布方法， 其特 征在于， 包括如下步骤： 确定数据流中数据待发布的直方图的区间； 对待的发布直方图的所有区间， 采用数据结构SES对当前时刻滑动窗口内的数据进行 采样， 获取当前时刻的采样集 合； 根据当前时刻的采样集 合， 获取当前时刻滑动窗口内所有区间的统计结果； 根据统计结果， 发布当前时刻滑动窗口 的直方图； 其中， 数据结构 SES对当前时刻滑动窗口内的数据进行采样的过程 为： 定义滑动窗口的大小 为w、 数据流 当前时刻 t的数据为et、 当前时刻数据流处于奇数滑动 窗口内数据的奇数采样集合S1、 当前时刻数据流偶数滑动窗口内数据的偶数采样集合S2、 采 样集合S， 所述 集合S1、 S2和S的大小均为s， 且w＞s； 当数据流进入第一个滑动窗口， 数据长度为1～w时， 采用局部水库采样获得奇数采样 集合S1， 并且采样集合S等于奇数采样集 合S1； 当数据流进入第二个滑动窗口， 数据长度为w+1～2w时， 采用局部水库采样获得偶数采 样集合S2； 所述采样集合S的构成为： 在任一时刻判断奇数采样集合S1是否存在元素过期， 删 除过期元素的奇数采样集合S1与偶数采样集合S2合并， 生成采样集合S； 当数据流进入第 二 个滑动窗口的当前时刻t为2w时， 奇数采样集合S1的元素全部过期， 当前时刻采样集合S等 于偶数采样集 合S2； 当数据流进入滑动窗口的当前时刻t>2w时， 划分数据流流入的滑动窗口为奇数窗口 (mod(fix(t /w),2)＝0)和偶数窗口(mod(fix(t/w),2)＝1)， 对任一奇数窗口或偶数窗口采 用局部水库采样， 获得每一时刻的采样集 合S； 所述局部水库采样的过程为： 对于数据流中位于滑动窗口前1～s位置的数据， 直接将 当前时刻的数据et放入对应的采样集合中； 对于数据流中位于滑动窗口后s～w位置的数 据， 为任一数据附加一随机因子r、 r∈[1， t]， 当r≤s， 将采样集合上与随机因子r位置对应 的元素替换为数据流当前时刻的数据， 否则保持采样集 合的数据不变。 2.根据权利要求1所述的具有差分隐私的在线流式采样 发布方法， 其特征在于， 对数据 流在任一时刻获得的所述采样集合S， 其包括数据流当前时间的元素、 所有区间的采样统计 结果和时间戳t； 对于1～w时刻范围内每一个时刻的采样集合S， 采用统计计数分别获得所有区间的采 样统计结果； 对于w+1～2w时刻范围、 t＞2w时刻下奇数窗口(mod(fix(t/w),2)＝0)和偶数窗口(mod (fix(t/w),2)＝1)范围内每一个时刻的采样集合S， 根据前一时刻所有区间的采样统计结 果和当前时刻的数据中是否有过期元素更正当前时刻每一个区间的统计结果， 对任一时刻 的滑动窗口有且仅有只有一个元 素过期。 3.根据权利要求2所述的具有差分隐私的在线流式采样 发布方法， 其特征在于， 所述获 取当前时刻滑动窗口内所有区间的统计结果的过程 为： 对当前时刻的采样集合S， 根据基础计数法对获得的采样集合的数据进行求和， 获得当 前时刻采样集合S内所有区间的统计结果， 记为{count1,count2,count3, …,countI}， 其 中， I为直方图所有可能的区间； 根据随机采用的性质， 估算当前时刻滑动窗口内所有区间的统计结果， 记为{count1,权　利　要　求　书 1/3 页 2 CN 115114584 A 2count2,count3, …,countI}*(w/s)。 4.根据权利要求1所述的具有差分隐私的在线流式采样 发布方法， 其特征在于， 发布的 所述当前时刻滑动窗口 的直方图满足( ε, δ ) ‑差分隐私。 5.一种具有差分隐私的在线流式采样发布系统， 其特 征在于， 包括： 确定模块， 用于确定数据流中数据待发布的直方图的区间； 采样模块， 用于对待的发布直方图的所有区间， 采用数据结构SES对当前时刻滑动窗口 内的数据进行采样， 获取当前时刻的采样集 合； 获取模块， 用于根据当前时刻的采样集合， 获取当前时刻滑动 窗口内所有区间的统计 结果； 发布模块， 用于根据统计结果， 发布当前时刻滑动窗口 的直方图； 其中， 采样模块实现采用数据结构SES对当前时刻滑动窗口内的数据进行采样的执行 单元包括： 定义单元， 用于定义滑动窗口的大小为w、 数据流当前时刻t的数据为et、 当前时刻数据 流处于奇数滑动窗口内数据的奇数采样集合S1、 当前时刻数据流偶数滑动窗口内数据的偶 数采样集 合S2、 采样集合S， 所述 集合S1、 S2和S的大小均为s， 且w＞s； 第一采样单元， 用于当数据流进入第一个滑动窗口， 数据长度为1～w时， 采用局部水库 采样获得奇数采样集 合S1， 并且采样集合S等于奇数采样集 合S1； 第二采样单元， 用于当数据流进入第二个滑动窗口， 数据长度为w+1～2w时， 采用局部 水库采样 获得偶数采样集合S2； 所述采样集合S的构 成为： 在任一时刻判断奇数采样集合S1 是否存在元素过期， 删除过期元素的奇数采样集合S1与偶数采样集合S2合并， 生成采样集合 S； 当数据流进入第二个滑动窗口的当前时刻t为2w时， 奇数采样集合S1的元素全部过期， 当 前时刻采样集 合S等于偶数采样集 合S2； 第三采样单元， 用于当数据流进入滑动窗口的当前时刻t>2w时， 划分数据流流入的滑 动窗口为奇数窗口(mod(fix(t /w),2)＝0)和偶数窗口(mod(fix(t/w),2)＝1)， 对任一奇数 窗口或偶数窗口采用局部水库采样， 获得每一时刻的采样集 合S； 其中， 局部水库采样的过程为： 对于数据流中位于滑动窗口前1～s位置的数据， 直接将 当前时刻的数据et放入对应的采样集合中； 对于数据流中位于滑动窗口后s～w位置的数 据， 为任一数据附加一随机因子r、 r∈[1， t]， 当r≤s， 将采样集合上与随机因子r位置对应 的元素替换为数据流当前时刻的数据， 否则保持采样集 合的数据不变。 6.根据权利要求5所述的具有差分隐私的在线流式采样 发布系统， 其特征在于， 所述采 样模块获取的当前时刻的采样集合包括数据流当前时间的元素、 所有区间的采样统计结果 和时间戳t， 所述所有区间的采样统计结果的获取 过程如下： 对于1～w时刻范围内每一个时刻的采样集合S， 采用统计计数分别获得所有区间的采 样统计结果； 对于w+1～2w时刻范围、 t＞2w时刻下奇数窗口(mod(fix(t/w),2)＝0)和偶数窗口(mod (fix(t/w),2)＝1)范围内每一个时刻的采样集合S， 根据前一时刻所有区间的采样统计结 果和当前时刻的数据中是否有过期元素更正当前时刻每一个区间的统计结果， 对任一时刻 的滑动窗口有且仅有只有一个元 素过期。 7.根据权利要求6所述的具有差分隐私的在线流式采样 发布系统， 其特征在于， 获取模权　利　要　求　书 2/3 页 3 CN 115114584 A 3