In this paper, we study the problem of publishing a stream of real-valued data satisfying differential privacy (DP). One major challenge is that the maximal possible value can be quite large; thus it is necessary to estimate a threshold so that numbers above it are truncated to reduce the amount of noise that is required to all the data. The estimation must be done based on the data in a private fashion. We develop such a method that uses the Exponential Mechanism with a quality function that approximates well the utility goal while maintaining a low sensitivity. Given the threshold, we then propose a novel online hierarchical method and several post-processing techniques. Building on these ideas, we formalize the steps into a framework for private publishing of stream data. Our framework consists of three components: a threshold optimizer that privately estimates the threshold, a perturber that adds calibrated noises to the stream, and a smoother that improves the result using post-processing. Within our framework, we design an algorithm satisfying the more stringent setting of DP called local DP (LDP). To our knowledge, this is the first LDP algorithm for publishing streaming data. Using four real-world datasets, we demonstrate that our mechanism outperforms the state-of-the-art by a factor of 6-10 orders of magnitude in terms of utility (measured by the mean squared error of answering a random range query).

本文研究了差分隐私下发布实数数据流的问题，并提出了一种基于指数机制和质量函数的私有阈值计算方法、在线分层方法和后处理技术。这个框架由三个组件组成：一个能私下计算阈  值的阈值优化器，一个在数据流中添加标定噪声的扰动器以及一个通过后处理来改善结果的远光镜。我们的算法考虑了更严格的本地差分隐私限制并超越了现有技术。使用四个真实数据集，展示了本方法比现有技术提高了6到10个数量级的实用性。

集中和本地差分隐私条件下的数据流连续发布