关键词: 差分隐私, 矩阵机制, 树状数组, 连续发布

Abstract: The vast majority of the literature on differential privacy algorithms focuses on one time static release of datasets, while many applications of data analysis involve the continual data release. This paper proposes a method based on matrix mechanism for differential privacy continual data release. The key idea of the proposed method is to firstly construct the strategy matrix of the continual data release problem using the binary indexed tree, and then optimize the strategy matrix to boost the accuracy of the published data. After that, aiming at the high time complexity of existing optimization algorithm based on matrix mechanism, this paper puts forward a fast diagonal matrix optimization algorithm (FDA) with O(lg N) time complexity, which can be applied to the situation of large-scale continuous data publishing effectively. This paper compares and analyzes FDA and the traditional algorithms on the accuracy of the released data by experiments. The experimental results show that FDA is effective and feasible.

Key words: differential privacy, matrix mechanism, binary indexed tree, continual data release