Privacy-preserving distributed k-means clustering over arbitrarily partitioned data

ABSTRACT

Advances in computer networking and database technologies have enabled the collection and storage of vast quantities of data. Data mining can extract valuable knowledge from this data, and organizations have realized that they can often obtain better results by pooling their data together. However, the collected data may contain sensitive or private information about the organizations or their customers, and privacy concerns are exacerbated if data is shared between multiple organizations.Distributed data mining is concerned with the computation of models from data that is distributed among multiple participants. Privacy-preserving distributed data mining seeks to allow for the cooperative computation of such models without the cooperating parties revealing any of their individual data items. Our paper makes two contributions in privacy-preserving data mining. First, we introduce the concept of arbitrarily partitioned data, which is a generalization of both horizontally and vertically partitioned data. Second, we provide an efficient privacy-preserving protocol for k-means clustering in the setting of arbitrarily partitioned data.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 2: J. Bar-Ilan , D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.201-209, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72995]
• 3: S. Benninga and B. Czaczkes. Financial Modelling. MIT Press, 1997.
• 4: R. R. de Carvalho, S. G. Djorgovski, N. Weir, U. Fayyad, J. Roden, A. Gray, and K. Cherkauer. Applications of clustering analysis and unsupervised classification algorithms to digitized POSS-II. Bulletin of the American Astronomical Society, 26:1372, December 1994.
• 5: E. Forgey. Cluster analysis of multivariate data: Efficiency vs. interpretability of classification. Biometrics, 21:768, 1965.
• 6: B. Goethals, S. Laur, H. Lipmaa, and T. Mielikainen. On secure scalar product computation for privacy-preserving data mining. In The 7th Annual International Conf. in Information Security and Cryptology, 2004.
• 7: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 8: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 9: Yehuda Lindell , Benny Pinkas, Privacy Preserving Data Mining, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.36-54, August 20-24, 2000
• 10: S. P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28:129--137, 1982.
• 11: J. MacQueen. Some methods for classification and analysis of multivariate observations. In Proc. Fifth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281--296, 1967.
• 12: Rob Mattison, Data Warehousing and Data Mining for Telecommunications, Artech House, Inc., Norwood, MA, 1997
• 13: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 14: S. Oliveira and O. R. Zaïane. Privacy preserving clustering by data transformation. In Proc. 18th Brazilian Symposium on Databases, pages 304--318, 2003.
• 15: Frank De Smet, Janick Mathys, Kathleen Marchal, Gert Thijs, Bart De Moor, and Yves Moreau. Adaptive quality-based clustering of gene expression profiles. Bioinformatics, 18(5):735--746, 2002.
• 16: Jaideep Vaidya , Chris Clifton, Privacy-preserving k-means clustering over vertically partitioned data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956776]
• 17: O. Veksler. Image segmentation by nested cuts. In Proc. of IEEE Computer Vision and Pattern Recognition, pages 339--344, 2000.
• 18: A. C.-C. Yao. How to generate and exchange secrets. In Proc. 27th IEEE Symp. on Foundations of Computer Science, pages 162--167, 1986.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Security