No Access

Differential privacy preserving clustering using Daubechies-2 wavelet transform

Department of Computer Engineering, Miyaneh Branch, Islamic Azad University, Miyaneh, Iran

and

School of Computer Engineering, Iran University of Science and Technology, Hengam St., Resalat Sq., Tehran 16846-13114, Iran

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0219691315500289Cited by:2 (Source: Crossref)

Abstract

Most of the existing privacy preserving clustering (PPC) algorithms do not consider the worst case privacy guarantees and are based on heuristic notions. In addition, these algorithms do not run efficiently in the case of high dimensionality of data. In this paper, to alleviate these challenges, we propose a new PPC algorithm, which is based on Daubechies-2 wavelet transform (D2WT) and preserves the differential privacy notion. Differential privacy is the strong notion of privacy, which provides the worst case privacy guarantees. On the other hand, most of the existing differential-based PPC algorithms generate data with poor utility. If we apply differential privacy properties over the original raw data, the resulting data will offer lower quality of clustering (QOC) during the clustering analysis. Therefore, we use D2WT for the preprocessing of the original data before adding noise to the data. By applying D2WT to the original data, the resulting data not only contains lower dimension compared to the original data, but also can provide differential privacy guarantee with high QOC due to less noise addition. The proposed algorithm has been implemented and experimented over some well-known datasets. We also compare the proposed algorithm with some recently introduced algorithms based on utility and privacy degrees.

Keywords:

AMSC: 22E46, 53C35, 57S20

References

C. C. Aggarwal and P. S. Yu (eds.) , Privacy-Preserving Data Mining: Models and Algorithms , series in Advances in Database Systems 34 ( Springer , Berlin, Heidelberg , 2008 ) . Crossref, Google Scholar
S. Agrawal, J. R. Haritsa and B. A. Prakash, Data Min. Knowl. Discov. 18(1), 101 (2009). Crossref, Web of Science, Google Scholar
F. Ahmed, R. Jin and A. X. Liu, A random matrix approach to differential privacy and structure preserved social network graph publishing, preprint (2013) , arXiv: 1307.0475 . Google Scholar
E. Bingham and H. Mannila, Random projection in dimensionality reduction: Applications to image and text data, Proc. 7th ACM SIGKDD Int. Conf. on Knowl. Discovery and Data Mining (ACM, NY, USA, 2001) pp. 245–250. Google Scholar
A. Blumet al., Practical privacy: The SuLQ framework, ACM SIGMOD/PODS 2005 Conference (ACM, NY, 2005) pp. 128–138. Google Scholar
A. Boggess and F. J. Narcowich , A First Course in Wavelets with Fourier Analysis , 1st edn. ( Prentice Hall , NJ , 2001 ) . Google Scholar
C. K. Chui , An Introduction to Wavelets ( Academic Press , MA , 1992 ) . Google Scholar
Y. Cui, W. K. Wong and D. W. Cheung, Privacy-preserving clustering with high accuracy and low time complexity, 14th Int. Conf. on Database Systems for Advanced Applications, DASSFAA 20095463, series in Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2009) pp. 456–470. Google Scholar
M. R. E. Dishabi and M. A. Azgomi, Intell. Data Anal. 18(4), 583 (2014). Crossref, Web of Science, Google Scholar
M. R. E. Dishabi, M. A. Azgomi and A. M. Rahmani, Int. J. Wavelets, Multiresolut. Inf. Process. 11(5), 1 (2013). Link, Web of Science, Google Scholar
C. Dwork, Differential privacy, Proc. of the 33rd Int. Colloquium on Automata, Languages and Programming (ICALP06) (Springer-Verlag, Berlin, 2006) pp. 1–12. Google Scholar
C. Dwork, Differential privacy: A survey of results, 5th International Conference (TAMC 2008) (2008) pp. 1–19. Google Scholar
C. Dworket al., Calibrating noise to sensitivity in private data analysis, TCC 2006 (2006) pp. 265–284. Google Scholar
C. Dwork and N. Nissim , Private representative-based clustering for vertically partitioned data , Proc. of CRYPTO ( Santa Barbara, California, USA , 2004 ) . Google Scholar
C. Dwork and A. Smith , J. Privacy Confident. 1 , 135 ( 2009 ) . Google Scholar
V. Estivill-Castro, Private representative-based clustering for vertically partitioned data, Proc. of the 5th Mexican Int. Conf. in Computer Science (2004) pp. 160–167. Google Scholar
A. Evfimievski, J. Gehrke and R. Srikant, Limiting privacy breaches in privacy preserving data mining, Proc. of the ACM Symp. on Principles of Database Systems (PODS) (San Diego, California, USA, 2003) pp. 211–222. Google Scholar
D. Feldmanet al., Private coresets, Proc. 41st Symp. on Theory of Computing (STOC) (2009) pp. 361–370. Google Scholar
B. C. M. Funget al., ACM Comput. Surv. 42(4), 14:1 (2010). Crossref, Web of Science, Google Scholar
S. Hajian and M. A. Azgomi, Intell. Data Anal. 15(4), 503 (2011). Crossref, Web of Science, Google Scholar
S. Hajian and M. A. Azgomi, Int. J. Wavelets, Multiresolut. Inf. Process. 9(6), 867 (2011). Link, Web of Science, Google Scholar
Z. Huang, W. Du and B. Chen, Deriving private information from randomized data, Proc. of the ACM SIGMOD Int. Conf. on Management of Data (ACM, NY, USA, 2005) pp. 37–48. Google Scholar
A. Inanet al., Data Knowl. Eng. 63(3), 646 (2007). Crossref, Web of Science, Google Scholar
Intelligent data storage for data-intensive analytical systems, http://uisacad2.uis.edu/ dstar/data/clusteringdata.html, Visited: 2014-2-26 . Google Scholar
G. Jagannathan , K. Pillaipakkamnatt and R. N. Wright , A new privacy-preserving distributed k-clustering algorithm , Proc. of the 2006 SIAM Int. Conf. on Data Mining ( 2006 ) . Google Scholar
S. Jha, L. Kruger and P. McDaniel, Privacy preserving clustering, Proc. of the 10th European Symp. on Research in Computer Security (2005) pp. 397–417. Google Scholar
W. Johnson and J. Lindenstrauss , Contemp. Math. 26 , 189 ( 1984 ) . Crossref, Google Scholar
S. V. Kayaet al., Efficient privacy preserving distributed clustering based on secret sharing, Proc. of the 2007 Int. Conf. on Emerging Technologies in Knowledge Discovery and Data Mining (Springer-Verlag, Berlin, Heidelberg, 2007) pp. 280–291. Google Scholar
W. Keller , Wavelets in Geodesy and Geodynamics ( Walter De Gruyter Inc. , 2004 ) . Crossref, Google Scholar
K. Kenthapadi, A. Korolova, I. Mironov and N. Mishra, Privacy via the Johnson-Lindenstrauss Transform, preprint (2012) , arXiv: 1204.2606 . Google Scholar
M. Klusch, S. Lodi and G. Moro, Distributed clustering based on sampling local density estimates, Proc. of the 18th Int. Joint Conf. on Artificial Intelligence (IJCAI 2003) (Acapulco, Mexico, 2003) pp. 485–490. Google Scholar
Machine Learning Repository, http://archive.ics.uci.edu/ml/datasets.html, Visited: 2014-02-26 . Google Scholar
F. McSherry, Privacy integrated queries: An extensible platform for privacy-preserving data analysis, SIGMOD 2009 (New York, USA, 2009) pp. 19–30. Google Scholar
S. Meregu and J. Ghosh, Privacy-preserving distributed clustering using generative models, Proc. of the 3rd IEEE Int. Conf. on Data Mining (ICDM'03) (2003) pp. 211–218. Google Scholar
S. Mukherjee, Z. Chen and A. Gangopadhyay, VLDB J. 15(4), 293 (2006). Crossref, Web of Science, Google Scholar
K. Nissim, S. Raskhodnikova and A. Smith, Smooth sensitivity and sampling in private data analysis, STOC 2007 (San Diego, California, USA, 2007) pp. 75–84. Google Scholar
S. R. M. Oliveira and O. R. Zaïane, Privacy preserving clustering by data transformation, Proc. of the 18th Brazilian Symp. on Databases (2003) pp. 304–318. Google Scholar
S. R. M. Oliveira and O. R. Zaïane, J. Comput. Secut. 26(1), 81 (2007). Crossref, Web of Science, Google Scholar
Y. Shen , J. Han and H. Shan , The research of privacy-preserving clustering algorithm , 3rd Int. Symp. Intelligent Information Technology and Security Informatics ( IEEE , 2010 ) . Google Scholar
K. P. Soman , K. I. Ramachandran and N. G Resmi , Insight Into Wavelets From Theory to Practice ( Prentice-Hall , 2011 ) . Google Scholar
J. Vaidya and C. Clifton, Privacy-preserving K-means clustering over vertically partitioned data, Proc. of the 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (2003) pp. 206–215. Google Scholar
D. F. Vysochanskij and Y. I. Petunin , Theor. Probab. Math. Statist. 21 , 25 ( 1980 ) . Google Scholar
X. Xiao, G. Wang and J. Gehrke, IEEE Trans. Knowl. Data Eng. 23(8), 1200 (2011). Crossref, Web of Science, Google Scholar
H. Zhanget al., J. Informatica 30(3), 305 (2006). Google Scholar