隐私保护关系型数据发布的多维划分动态规划算法

A dynamic programming algorithm based on multidimensional partitioning for privacy preserving relational data publishing

目前大部分隐私保护关系型数据发布算法均未能有效兼顾算法效率和发布数据的可用性.从空间多维划分的角度研究关系型数据发布中的隐私保护问题,发现前期研究提出的基于子空间划分的隐私保护最优k-匿名动态规划算法(k-ASPDP)可适用于多种隐私保护机制,进而设计出一种基于多维划分的隐私保护关系型数据发布动态规划算法框架Bottom-Up MG,并针对动态规划算法k-ASPDP空间复杂度较大的不足,提出一个空间可扩展性强的混合k-匿名化算法k-ASPDP+.实验分别对以l-多样性为隐私保护机制的Bottom-Up MG算法和k-ASPDP+算法所发布数据的可用性及算法效率与同类算法进行比较分析.实验结果表明,本文算法是有效可行的.

Recently,privacy preserving data publishing has been a hot topic in data privacy preserving research fields.The goal of privacy preserving data publishing is to propose safe and effective algorithms for data processing before data releasing,while ensuring high utility of the released data.However,most of the previous works on privacy preserving relational data publishing can not effectively take into account the algorithm efficiency and the availability of publishing data.In this paper,we revisit privacy preserving relational data publishing from the perspective of space multidimensional partitioning.It is found that subspace partitioning based dynamic programming algorithm k-ASPDP designed in our previous work for optimal k-anonymization can be applied to multiple privacy preserving mechanisms.Based on this,a dynamic programming algorithm framework Bottom-Up MG based on multidimensional partitioning for privacy preserving relational data publishing is presented in this paper.After that,in order to overcome the deficiency of high space complexity of the dynamic programming algorithm k-ASPDP,we propose a hybrid k-anonymous algorithm k-ASPDP＋ with high spatial scalability.Experimental analysis are designed by comparing Bottom-Up MG under l-diversity privacy preserving mechanism as well as k-ASPDP＋ and the traditional algorithm on the released data availability and the algorithm efficiency.Experimental results show that the proposed algorithms in this paper are effective and feasible.