Distributed privacy preserving k-means clustering with additive secret sharing

Doğanay, Mahir Can and Pedersen, Thomas Brochmann and Saygın, Yücel and Savaş, Erkay and Levi, Albert (2008) Distributed privacy preserving k-means clustering with additive secret sharing. In: Proceedings of the 2008 International Workshop on Privacy and Anonymity in Information Society, PAIS 2008,, Nantes, France

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Recent concerns about privacy issues motivated data mining researchers to develop methods for performing data mining while preserving the privacy of individuals. However, the current techniques for privacy preserving data mining suffer from high communication and computation overheads which are prohibitive considering even a modest database size. Furthermore, the proposed techniques have strict assumptions on the involved parties which need to be relaxed in order to reflect the real-world requirements. In this paper we concentrate on a distributed scenario where the data is partitioned vertically over multiple sites and the involved sites would like to perform clustering without revealing their local databases. For this setting, we propose a new protocol for privacy preserving k-means clustering based on additive secret sharing. We show that the new protocol is more secure than the state of the art. Experiments conducted on real and synthetic data sets show that, in realistic scenarios, the communication and computation cost of our protocol is considerably less than the state of the art which is crucial for data mining applications.

Item Type:Papers in Conference Proceedings
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:10239
Deposited By:Erkay Savaş
Deposited On:08 Nov 2008 16:07
Last Modified:22 Jul 2019 09:07

Repository Staff Only: item control page