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

[thumbnail of published_p3-doganay.pdf] PDF

Download (227kB)


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 08 Nov 2008 16:07
Last Modified: 26 Apr 2022 08:47
URI: https://research.sabanciuniv.edu/id/eprint/10239

Actions (login required)

View Item
View Item