基于矩阵机制的差分隐私连续数据发布方法  

Method Based on Matrix Mechanism for Differential Privacy Continual Data Release

作　　者：蔡剑平[1] 吴英杰[1] 王晓东[1] 

机构地区：[1]福州大学数学与计算机科学学院,福州350116

出　　处：《计算机科学与探索》2016年第4期481-494,共14页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.61300026;福建省自然科学基金No.2014J01230~~

摘　　要：现有绝大多数差分隐私算法只考虑数据的一次静态发布,而实际许多数据分析应用却涉及连续数据发布。为此,提出了一种基于矩阵机制的差分隐私连续数据发布方法。该方法的核心思想是首先利用树状数组构建连续数据发布问题的策略矩阵,然后对策略矩阵进行优化以提高发布数据的精确性。随后,进一步针对现有基于矩阵机制的优化算法复杂度极高的问题,提出了时间复杂度为O(lg N)的快速对角阵优化算法(fast diagonal matrix optimization algorithm,FDA),以有效应用于大规模的连续数据发布。通过实验比较分析了FDA算法与同类算法所发布数据的精确度,结果表明FDA算法是有效可行的。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.

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

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]