(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210343677.X (22)申请日 2022.03.31 (71)申请人 安徽工业大学 地址 243032 安徽省马鞍山市湖东中路59 号 申请人 合肥综合 性国家科 学中心人工智能 研究院 （安徽省人工智能实验室） (72)发明人 王修君　莫磊　郑啸　何诗兴　 (74)专利代理 机构 南京九致知识产权代理事务 所(普通合伙) 32307 专利代理师 王晓青 (51)Int.Cl. G06F 17/18(2006.01) G06F 21/62(2013.01) G06F 16/2458(2019.01)G16H 10/60(2018.01) (54)发明名称 一种差分隐私下加权滑动窗口的流式直方 图发布方法及系统 (57)摘要 本发明提供一种差分隐私下加权滑动窗口 的流式直方图发布方法及系统， 涉及信息安全技 术领域； 本发明首先创建了一个新的草图结构， 维护每个时间实例的每个直方图区间的计数信 息； 然后， 本发明提出一种选 择性发布机制， 该机 制利用每个直方图区间近似估计的区间计数值 与噪声值之间的差异来选择更好的计数信息， 并 在加权滑动窗口中对所有的间隔计数采用贪婪 分组， 保证了大多数情况下查询数据的竞争性可 用性。 本发 明可以快速处理基于加权滑动窗口的 数据流， 并在大多数情况下保证发布数据的竞争 性可用性。 权利要求书4页 说明书13页 附图9页 CN 114969656 A 2022.08.30 CN 114969656 A 1.一种差分隐私下加权滑动窗口 的流式直方图发布方法， 其特 征在于， 包括： 确定数据流中数据待发布的加噪直方图的区间； 确定最优的隐私预算分配因子α， 分配整体隐私预算ε为第 一部分隐私预算α ε和第二部 分隐私预算 ε(1 ‑α )； 对待发布的加噪直方图的每一个区间， 构建近似估算草图结构对加权滑动窗口中的数 据进行近似 估计， 获得 所有区间的区间计数值； 对待发布的加噪直方图添加第 一隐私预算α ε， 分别获得每个区间的第 一部分隐私预算 噪声值； 根据待发布的加噪直方图任一区间的区间计数值与其对应的第一部分隐私预算噪声 值确定各区间的近似统计频数， 根据各区间的近似统计频数构建当前时刻近似统计直方 图； 采用第二部分隐私预算ε(1 ‑α )根据贪心聚类算法对当前时刻近似统计直方图排序后 的区间进行聚类处 理， 获得当前时刻滑动窗口 的加噪直方图； 发布当前时刻滑动窗口 的加噪直方图。 2.根据权利要求1所述的差分隐私下加权滑动 窗口的流式直方图发布方法， 其特征在 于， 所述隐私预算分配因子α 的确定方法为： 采用小样本进行 预处理， 对隐私预算分配因子α 设定不同取值； 分别计算待发布的加噪直方图的每一个区间在各取值下的加噪值与真实值之间的均 方误差； 选择最小均方误差对应的隐私预算分配因子的取值 为最优的隐私预算分配因子α 。 3.根据权利要求1所述的差分隐私下加权滑动 窗口的流式直方图发布方法， 其特征在 于， 所述构建近似估算草图结构对加权滑动窗口中的数据进行近似估计， 获得区间计数值 的过程为： 判断进入加权滑动 窗口数据流的当前数据是否符合待发布的加噪直方图判断统计的 区间； 若当前数据满足当前区间范围， 当前数据置为 1； 若当前数据不满足当前区间范围， 当 前数据置为0； 对加权滑动窗口分块， 计算加权滑动 窗口的近似误差阈值θ和当前时间戳的加权计数 值y， 计算公式分别为： y＝y×γ+xt； 其中， W表示滑动窗口的大小， γ表示加 权因子， β 表示近似误差因子， Si[t‑W+1,t]表示第i个二进制数据流的滑动窗口， xt表示当前 时刻滑动窗口Si[t‑W+1,t]中的一个元 素实例； 判断数据流Si[t‑W+1,t]在当前时间戳上 是否有存在过期数据元 素； 计算当前时间戳的区间计数值 当数据流Si[t‑W+1,t]在当前时间戳 上生成过期数据 元素， 则 当数据流Si[t‑W+1,t]在当前 时间戳上没有过期数据 元素， 则 其中， B表示一个用于存储加权 滑动窗口计数信息的二维数组， 其中， B1(i)表示第一个子数组、 记录数据流中当前元素的 时间戳， B2(i)表示第二个子数组、 存储第i个二进制数据流Si[t‑W+1,t]的区间计数值 权　利　要　求　书 1/4 页 2 CN 114969656 A 2old(B1(i))表示最老块第一个子数组， o ld(B2(i))表示最老块第二个子数组； 判断当前时间戳的区间计数值 的大小， 将区间计数值 小于0的结果， 全部置为0， 获 得当前加权滑动窗口内所有区间计数值 4.根据权利要求3所述的差分隐私下加权滑动 窗口的流式直方图发布方法， 其特征在 于， 所述根据待发布的加噪直方图任一区间的区间计数值与其对应的第一部分隐私预算噪 声值确定各区间的近似统计频 数的过程 为： 判断近似误差与噪音阈值的大小， 确定近似统计频数； 其中， 近似误差为区间计数值与 真实值的差值， 噪音阈值表示第一部分隐私预算噪声值与真实值的最大差值 当近似误差阈值小于噪音阈值， 近似统计频 数为区间计数值 当噪音阈值小于近似误差， 近似统计频数为加噪值， 即 其中， Gi表示待 发布的加噪直方图计算区间的真实值； 判断近似统计频数的大小， 将近似统计频数小于0的结果， 全部置为0， 获得当前加权滑 动窗口内所有区间的近似统计频 数。 5.根据权利要求4所述的差分隐私下加权滑动 窗口的流式直方图发布方法， 其特征在 于， 所述采用第二部 分隐私预算 ε(1 ‑α )根据贪心聚类算法对当前时刻近似统计直方图排序 后的区间进行聚类处 理的过程 为： 根据排序算法对加权滑动窗口内所有区间 的近似统计频数 进行排序， 并计算每一个 频数与其他频数之间合并的误差以及不 合并的误差； 判断区间分组， 包括： 当两个区间合并误差小于不合并误差， 将这两个区间进行合并， 并设为一组； 当两个区间合并误差大于不合并误差， 将这两个区间不进 行合并， 并设为两个 组； 其中， 合并误差为区间间隔与区间间隔之 间进行合并， 每个区间的平均值与每个区间的 当前值进行平方差的结果； 不合并误差为区间间隔与区间间隔之间不进行合并， 每个区间 的平均值与每 个区间的现有值进行平方差的结果； 对当前加权滑动窗口内所有区间进行重新分组； 使用每个分组平均值取代每个分组 的近似统计频数值， 并通过每一个分组中的近似统 计频数值占整个加权滑动窗口内数据统计值总数的比例确定每一个区间的第二部分隐私 预算， 以便对各分组区间添加拉普拉斯噪音； 计算添加拉普拉斯噪音后各分组的近似统计频数， 判断近似统计频数的大小， 将近似 统计频数小于0的结果， 全部 置为0； 获得当前时刻滑动窗口 的加噪直方图。 6.根据权利要求5所述的差分隐私下加权滑动 窗口的流式直方图发布方法， 其特征在 于， 所述区间分组的具体过程 为： 对排序后近似统计直方图的第 一个区间自成一组， 判断第 二个区间加入当前分组后引 入的噪音误差与以第二个区间为起点重新建立的新分组引入的噪音误差的大小； 若加入当 前分组比建立一个新分组引入的噪音误差小， 则加入当前分组， 否则建立一个新分组； 直至权　利　要　求　书 2/4 页 3 CN 114969656 A 3