Affiliations: [a] School of Geography and Tourism, Anhui Normal University, Wuhu, Anhui 241003,
China | [b] Anhui Provincial Key Laboratory of Network
and Information Security, Anhui Normal University, Wuhu, Anhui 241003,
China
Correspondence:
[*]
Corresponding author: Yonglong Luo, School of Geography and Tourism, Anhui Normal University, Wuhu, Anhui 241003, China. Tel.: +86 0553 5910645; E-mail: ylluo@ustc.edu.cn.
Abstract: Data needs to be released to the relevant decision makers and researchers. Privacy protection should be carried out first because it contains personal sensitive information. The k-anonymity algorithm is an important privacy protection algorithm, and partitioning is one of its key methods. To reduce the computational complexity and low speed of existing privacy-preserving algorithms for high-dimensional data publishing, a probabilistic optimal projection partition k-dimensional (KD)-tree k-anonymity algorithm is proposed. First, some attribute dimensions are probabilistically selected from the global domain. Then, for these dimensions, the partition coefficient is calculated and the optimal partition point is determined. Furthermore, an improved KD-tree structure is introduced in which a node is a collection rather than a data point. The proposed KD-tree node is divided into left and right child nodes by the hyper-plane passing through the dividing point and perpendicular to the optimal dimension. The proposed algorithm is validated by a theoretical analysis and comparison experiments. The results show that the proposed algorithm can reduce the average generalization range by 11% to 22% compared to traditional k-anonymity. This enables better division and better dataset availability. Moreover, the runtime is reduced by 8% to 32% compared to globally optimal projection partitioning k-anonymity.
Keywords: Data publishing, privacy protection, k-anonymity, KD-tree, probabilistic partitioning
