Adaptive Histogram Publishing Algorithm for Sliding Window of Data Stream

Abstract

As one of the most effective privacy protection mechanisms,differential privacy has been widely used in many fields.The existing histogram publishing methods for either static data set or dynamic data set mainly protect the privacy of sliding windows in data streams by adding unified noise.This leads to low data availability,high time complexity and weak privacy protection in their practical applications.In this paper,we tackle this problem by integrating the approximate counting techniques into the differential privacy and proposing an adaptive histogram publishing method for sliding window(APS).Firstly,the proposed APS predicates the distributional information of the sliding windows in the data stream by using an approximate counting method.Secondly,it computes an appropriate value suitable for publishing by checking the difference between estimated values and actual values.Finally,it reduces statistical errors within each interval by clustering.Theoretical analysis shows that the APS algorithm can effectively improve data availability and reduce running time while reducing the privacy budget.Experimental results on two different real data sets also verify the superiority of APS algorithm over existing grouping-based histogram publishing algorithms in terms of data availability and running time.

Keywords

• differential privacy|sliding window|data stream|histogram publishing|approximation error|laplacian error