Probabilistic optimal projection partition KD-Tree k -anonymity for data publishing privacy protection

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

Get full access to this article

View all access options for this article.

References

Chakraborty

and Tripathy

B.K.

, Privacy preserving anonymization of social networks using eigenvector centrality approach, Intell. Data Anal 20 (2016), 543–560.

Rajalaxmi

R.R.

and Natarajan

A.M.

, Effective sanitization approaches to hide sensitive utility and frequent itemsets, Intell. Data Anal 16 (2012), 933–951.

Lin

C.Y.

Kao

Y.H.

Lee

W.B.

and Chen

R.C.

, An efficient reversible privacy-preserving data mining technology over data streams, Springer Plus 5 (2016), 1047–1057.

T.C.

N.H.

Zhang

and Molloy

, Slicing: A new approach for privacy preserving data publishing, IEEE Transactions on Knowledge and Data Engineering 24 (2012), 561–574.

Fung

B.C.M.

Wang

L.Y.

and Hung

P.C.K.

, Privacy-preserving data publishing for cluster analysis, Data & Knowledge Engineering 68 (2009), 552–575.

Fung

B.C.M.

Wang

Chen

and Yu

P.S.

, Privacy-preserving data publishing: a survey of recent developments, ACM Computing Surveys 42 (2010), 53.

Nayahi

J.J.V.

and Kavitha

, Privacy and utility preserving data clustering for data anonymization and distribution on Hadoop, Future Generation Computer Systems-the International Journal of Escience 74 (2017), 393–408.

Gong

Yang

Chen

and Luo

, A framework for utility enhanced incomplete microdata anonymization, Cluster Computing-the Journal of Networks Software Tools and Applications 20 (2017), 1749–1764.

et al., A hybrid approach to prevent composition attacks for independent data releases, Information Sciences 367 (2016), 324–336.

10.

Sweeney

, Achieving k-anonymity privacy protection using generalization and suppression, International Journal of Uncertainty Fuzziness and Knowledge-Based Systems 10 (2002), 571–588.

11.

Sweeney

, k-anonymity: A model for protecting privacy, International Journal of Uncertainty Fuzziness and Knowledge-Based Systems 10 (2002), 557–570.

12.

Newton

E.M.

Sweeney

and Malin

, Preserving privacy by de-identifying face images, IEEE Transactions on Knowledge and Data Engineering 17 (2005), 232–243.

13.

Zhou

and Pei

, The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks, Knowledge and Information Systems 28 (2011), 47–77.

14.

Rebollo-Monedero

Forne

and Domingo-Ferrer

, From t-closeness-like privacy to postrandomization via information theory, IEEE Transactions on Knowledge and Data Engineering 22 (2010), 1623–1636.

15.

N.H.

T.C.

and Venkatasubramanian

, Closeness: A new privacy measure for data publishing, IEEE Transactions on Knowledge and Data Engineering 22 (2010), 943–956.

16.

Tang

and Tian

, A survey of privacy preserving data publishing using generalization and suppression, Applied Mathematics & Information Sciences 8 (2014), 1103–1116.

17.

Gong

Q.Y.

Luo

J.Z.

Yang

W.W.

and Li

X.B.

, Anonymizing 1:M microdata with high utility, Knowledge-Based Systems 115 (2017), 15–26.

18.

W.W.

M.Z.

and Chen

, Location privacy-preserving k nearest neighbor query under user’s preference, Knowledge-Based Systems 103 (2016), 19–27.

19.

Zhu

Tian

and Xie

, Anonymization on Refining Partition: Same Privacy, More Utility, Computer Science and Information Systems 12 (2015), 1193–1216.

20.

Matatov

Rokach

and Maimon

, Privacy-preserving data mining: A feature set partitioning approach, Information Sciences 180 (2010), 2696–2720.

21.

Kumar

and Minz

, Multi-view ensemble learning: an optimal feature set partitioning for high-dimensional data classification, Knowledge and Information Systems 49 (2016), 1–59.

22.

Sarrafi Aghdam and Sonehara

, Achieving high data utility k-anonymization using similarity-based clustering model, IEICE Transactions on Information and Systems E99D (2016), 2069–2078.

23.

Gkoulalas-Divanis

Loukides

and Sun

, Publishing data from electronic health records while preserving privacy: A survey of algorithms, Journal of Biomedical Informatics 50 (2014)., 4–19.

24.

Park

and Shim

, Approximate algorithms with generalizing attribute values for k-anonymity, Information Systems 35 (2010), 933–955.

25.

Lefevre

Dewitt

D.J.

, and Ramakrishnan

, Mondrian Multidimensional K-Anonymity, in International Conference on Data Engineering, 2006, 25–25.

26.

Y.J.

Tang

Q.M.

and Ni

W.W.

, Algorithm for k-anonymity based on rounded partition function, Journal of Software 23 (2012), 2138–2148.

27.

Wang

Yang

Zhang

J.P.

and Lv

, Algorithm for k-anonymity based on projection area density partition, Journal on Communications 36 (2015), 125–134.

28.

Wang

X.H.

Luo

Y.L.

and Jiang

Y.F.

, An optimal projection partition k-anonymity algorithm of KD-tree, Journal of Nanjing University 52 (2016), 1050–1064.

29.

Herranz

Nin

and Sole

, Kd-trees and the real disclosure risks of large statistical databases, Inf. Fusion 13 (2012), 260–273.

30.

Popov

Guenther

Seidel

H.-P.

and Slusallek

, Stackless KD-Tree traversal for high performance GPU ray tracing, Comput. Graph. Forum 26 (2007), 415–424.

31.

Redmond

S.J.

and Heneghan

, A method for initialising the K-means clustering algorithm using kd-trees, Pattern Recognit. Lett. 28 (2007), 965–973.