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

作     者：王修君 莫磊 郑啸 卫琳娜 董俊 刘志 郭龙坤 Wang Xiujun;Mo Lei;Zheng Xiao;Wei Linna;Dong Jun;Liu Zhi;Guo Longkun

作者机构：安徽工业大学计算机科学与技术学院安徽马鞍山243032 安徽省工业互联网智能应用与安全工程研究中心(安徽工业大学)安徽马鞍山243032 福州大学数学与统计学院福州350108 中国科学院合肥物质科学研究院智能机械研究所合肥230031 电气通信大学日本东京163-8001 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2024年第61卷第10期

页      面：2433-2447页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(62172003,12271098,61772005) 安徽省自然科学基金项目(2108085MF218,2108085MF217) 安徽省高校自然科学研究项目(2022AH040052) 马鞍山市科技创新项目(2021a120009) 

主　　题：云原生数据库 滑动窗口 数据流 差分隐私 数据采样 数据发布 

摘      要：基于云原生数据库的许多应用场景需要处理海量的数据流.为了实时分析数据流中的群体趋势信息而又不泄露单个用户的隐私,这些应用需要在每个时刻都可以为数据流中的最近数据集快速创建可以安全发布的差分隐私直方图.然而,现有的直方图发布方法因缺乏高效数据结构,导致无法快速提取关键信息以确保数据的实时可用性.为解决此问题,深入分析数据采样与隐私保护之间的关系,提出基于采样的数据流差分隐私快速发布算法SPF(sampling based fast publishing algorithm with differential privacy for data stream).SPF首创高效数据流采样草图结构(efficient data stream sampling sketch structure,EDS),EDS对滑动窗口内数据进行采样统计估计,并过滤不合理数据,实现了对关键信息的快速提取.然后,证明EDS结构输出的近似值理论上等效于对真实值添加差分隐私噪声.最后,为了满足用户所提供的隐私保护强度,并且避免正确反映原始数据流的真实情况,提出了一种基于高效数据流采样的自适应加噪算法.根据用户的隐私保护强度和EDS结构所提供的隐私保护强度之间的关系,通过隐私分配的方式自适应生成最终可发布直方图.实验证明,相较于现有算法,SPF在保持相同数据可用性的前提下显著降低了时间和空间开销.