Privacy-preserving <i>k</i> -means clustering over vertically partitioned data
Published 24 August 2003
Jaideep Vaidya, Chris Clifton
Citations631
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work presents a method for k-means clustering when different sites contain different attributes for a common set of entities, where each site learns the cluster of each entity, but learns nothing about the attributes at other sites.
Abstract
Privacy and security concerns can prevent sharing of data, derailing data mining projects. Distributed knowledge discovery, if done correctly, can alleviate this problem. The key is to obtain valid results, while providing guarantees on the (non)disclosure of data. We present a method for k-means clustering when different sites contain different attributes for a common set of entities. Each site learns the cluster of each entity, but learns nothing about the attributes at other sites.
Keywords
Computer ScienceDecision Sciences
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Elsevier eBooksIntroduction to Statistical Pattern Recognition
11,121 Citations1990Keinosuke Fukunaga
A system to determine the sex of fish from their length, as accurately as possible, using a set of labelled data, together with the class label (male or female), as a training set.
Lecture notes in computer sciencePublic-Key Cryptosystems Based on Composite Degree Residuosity Classes
7,186 Citations2007Pascal Paillier
A new trapdoor mechanism is proposed and three encryption schemes are derived : a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to RSA, which are provably secure under appropriate assumptions in the standard model.
TechnometricsThe EM Algorithm and Extensions
5,108 Citations1998Debashis Kushary, Geoffrey J. McLachlan +1 more
How to generate and exchange secrets
3,712 Citations1986Andrew Chi-Chih Yao
It is shown how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors, is hidden from either party individually but is recoverable jointly if desired.
How to play ANY mental game
3,541 Citations1987Oded Goldreich, Silvio Micali +1 more
This work presents a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest.
ACM SIGMOD RecordPrivacy-preserving data mining
2,993 Citations2000Rakesh Agrawal, Ramakrishnan Srikant
Privacy-preserving data mining
1,706 Citations2000Rakesh Agrawal, Ramakrishnan Srikant
This work considers the concrete case of building a decision-tree classifier from training data in which the values of individual records have been perturbed, and proposes a novel reconstruction procedure to accurately estimate the distribution of original data values.
Lecture notes in computer sciencePrivacy Preserving Data Mining
1,027 Citations2000Yehuda Lindell, Benny Pinkas
On the design and quantification of privacy preserving data mining algorithms
1,018 Citations2001Dakshi Agrawal, Charų C. Aggarwal
It is proved that the EM algorithm converges to the maximum likelihood estimate of the original distribution based on the perturbed data, and proposed metrics for quantification and measurement of privacy-preserving data mining algorithms are proposed.
Privacy preserving association rule mining in vertically partitioned data
1,009 Citations2002Jaideep Vaidya, Chris Clifton
This paper presents a two-party algorithm for efficiently discovering frequent itemsets with minimum support levels, without either site revealing individual transaction values.
Refining Initial Points for K-Means Clustering
999 Citations1998Paul S. Bradley, Usama M. Fayyad
A procedure for computing a refined starting condition from a given initial one that is based on an efficient technique for estimating the modes of a distribution that allows the iterative algorithm to converge to a “better” local minimum.
Privacy-preserving distributed mining of association rules on horizontally partitioned data
890 Citations2010Murat Kantarcıoğlu, Chris Clifton +2 more
Privacy preserving mining of association rules
785 Citations2002Alexandre Evfimievski, Ramakrishnan Srikant +2 more
A class of randomization operators are proposed that are much more effective than uniform randomization in limiting the breaches of privacy breaches and derived formulae for an unbiased support estimator and its variance are derived.
Lecture notes in computer scienceA new public-key cryptosystem as secure as factoring
672 Citations1998Tatsuaki Okamoto, Shigenori Uchiyama
This paper proposes a novel public-key cryptosystem, which is practical, provably secure and has some other interesting properties as follows: It can be proven to be as secure as the intractability of factoring n = p2q (in the sense of the security of the whole plaintext) against passive adversaries.
Elsevier eBooksMaintaining Data Privacy in Association Rule Mining
492 Citations2002Shariq J. Rizvi, Jayant R. Haritsa
This work presents a scheme, based on probabilistic distortion of user data, that can simultaneously provide a high degree of privacy to the user and retain a high level of accuracy in the mining results.
The EM algorithm and extensions
452 Citations1997McLachlan, Geoffrey J, Krishnan, Thriyambakam
Secure multi-party computation problems and their applications
440 Citations2001Wenliang Du, Mikhail J. Atallah
A framework is developed to identify and define a number of new SMC problems for a spectrum of computation domains that include privacy-preserving database query, privacy- Preserving scientific computations, Privacy-Preserving intrusion detection,privacy-preserve statistical analysis, privacy -preserving geometric computation, and privacy- preserving data mining.
Lecture notes in computer scienceA Data-Clustering Algorithm on Distributed Memory Multiprocessors
386 Citations2002Inderjit S. Dhillon, Dharmendra S. Modha
To cluster increasingly massive data sets that are common today in data and text mining, a parallel implementation of the k-means clustering algorithm based on the message passing model is proposed and analytically shows that the speedup and the scaleup of the algorithm approach the optimal as the number of data points increases.
A new public key cryptosystem based on higher residues
360 Citations1998David Naccache, Jacques Stern
The probabilistic version of the scheme is an homomorphic encryption scheme whose expansion rate is much better than previously proposed such systems and has se- mantic security, relative to the hardness of computing higher residues for suitable moduli.
Privacy-preserving cooperative statistical analysis
282 Citations2005Wenliang Du, Mikhail J. Atallah
Protocols for conducting the statistical analysis in such a cooperative environment based on a data perturbation technique and cryptography primitives are developed.
Selected Areas in CryptographyDense Probabilistic Encryption
253 Citations1999Josh Benaloh
A method of probabilistic encryption in which the ratio of ciphertext text size to plain text size and the proportion of random bits to plaintext can both be made arbitrarily close to one is developed.
Knowledge and Information SystemsDistributed Clustering Using Collective Principal Component Analysis
163 Citations2001Hillol Kargupta, Weiyun Huang +2 more
A way to integrate the Collective PCA with a given off-the-shelf clustering algorithm in order to develop a distributed clustering technique.
IEEE Transactions on Knowledge and Data EngineeringPrivacy-preserving distributed mining of association rules on horizontally partitioned data
152 Citations2004Murat Kantarcıoğlu, Chris Clifton
This work addresses secure mining of association rules over horizontally partitioned data by incorporating cryptographic techniques to minimize the information shared, while adding little overhead to the mining task.
Knowledge and Information SystemsPrivacy-preserving clustering with distributed EM mixture modeling
152 Citations2004X. Sheldon Lin, Chris Clifton +1 more
A technique that uses EM mixture modeling to perform clustering on distributed data that controls data sharing, preventing disclosure of individual data items or any results that can be traced to an individual site.
Robust space transformations for distance-based operations
49 Citations2001Edwin M. Knorr, Raymond T. Ng +1 more
The fundamental question that this paper addresses is: "What then is an appropriate space?" and this paper proposes using a robust space transformation called the Donoho-Stahel estimator, which says that in spite of frequent updates, the estimator does not lose its usefulness, or require re-computation.
An architecture for privacy-preserving mining of client information
31 Citations2002Murat Kantarcıoğlu, Jaideep Vaidya
This paper presents a general architecture that enables privacy-preserving mining of client information, and shows that the methods are secure, while maintaining the accuracy of the results.