基于差分隐私的流式直方图发布关键技术研究

Based on histograms, obtaining fast and accurate sketches of data distributions is a central problem in data stream analysis and query. However, directly releasing the results from analysis and query will lead to privacy leakage. Traditional privacy-preserving models (e.g., k-anonymity, l-diversity, etc.) cannot cover the connotation of the privacy of data stream. In this project, we intend to conduct a comprehensive study on dynamic histogram publication over data streams under differential privacy, the de facto standard for privacy protection. We will propose a dual-clustering-based framework for publishing continuous histograms over data streams. More specifically, we will design a bin-clustering-based strategy for releasing static histograms, develop a time-clustering-based sanitization method for publishing dynamic sliding window histograms by means of adaptive sampling, and explore constrained inference techniques to boost utility. Our results will be used to build a prototype system in order to validate the effectiveness and scalability of our solution on both synthetic and real-life data streams. These studies will provide new ideas, theoretical methods and technical support for further research on differential privacy.

利用直方图快速而又准确地获取数据分布的梗概是数据流分析与查询的主要任务之一。然而，直接发布分析或者查询结果无法避开的事实是隐私问题。传统的隐私保护方法（例如k-anonymity、l-diversity等）无法涵盖数据流隐私的实际内涵。本项目采用作为业界标准的差分隐私模型对数据流直方图发布进行系统性研究，旨在提出基于双聚类的动态数据流直方图发布框架。具体拟研究基于桶聚类的静态直方图发布策略，在此基础上研究自适应抽样的基于时间粒度聚类的滑动窗口直方图发布方法，并探讨基于约束推理的数据可用性提升方法。研究成果将用于搭建基于差分隐私的数据流直方图发布原型系统以验证提出方案在真实数据和模拟数据上的有效性和高效性。通过本项目的研究为差分隐私保护技术进一步深入研究与应用提供理论方法、技术支撑和新的思路。

差分隐私已成为隐私保护领域研究的热点。本项目结合直方图发布带来的系列隐私问题，研究基于差分隐私的静态与流式直方图发布方案。项目组取得了一些研究成果：申请授权专利2项，发表或录用论文14篇。项目组代表性成果包括：（a）提出了一种基于自适应采样与滑动窗模型的流式直方图发布方法；（b）提出了一种基于蒙特卡洛抽样与指数机制的静态直方图发布方法；（3）提出了一种基于阈值过滤与三层网格结构的空间直方图发布方法；（4）提出了一种基于阈值过滤与马尔科夫网络的高维直方图发布方法；（5）提出了两种基于傅里叶变换与矩阵变换的人脸图像发布方法。这些研究成果为基于数据流服务中隐私保护问题的进一步研究与应用奠定基础，提供了新的思路。