DocumentCode :
3061519
Title :
Multi-party k-Means Clustering with Privacy Consideration
Author :
Yu, Teng-Kai ; Lee, D.T. ; Chang, Shih-Ming ; Zhan, Justin
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
fYear :
2010
fDate :
6-9 Sept. 2010
Firstpage :
200
Lastpage :
207
Abstract :
The k-means clustering algorithm is a widely used scheme to solve the clustering problem which classifies a given set of n data points in m-dimensional space into k clusters, whose centers are obtained by the centroids of the points in the same cluster. The problem with privacy consideration has been studied, when the data is distributed among different parties and the privacy of the distributed data is to be preserved. In this paper, we apply the concept of parallel computing to solve the privacy-preserving multi-party k-means clustering problem, when the data is vertically partitioned and horizontally partitioned respectively among different parties. We present algorithms for solving the problems for these two data partition models that run in O(nk) time and in O(m(k + log(n=k))) time respectively. The time complexities of the algorithms are much better than others without parallel computing.
Keywords :
computational complexity; data privacy; parallel processing; pattern clustering; data partition models; multi party k-means clustering; parallel computing; privacy consideration; time complexities; Clustering algorithms; Complexity theory; Data models; Data privacy; Encryption; Parallel processing; Partitioning algorithms; PPDM; clustering; k-means; parallel computing; privacy-preserving;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing with Applications (ISPA), 2010 International Symposium on
Conference_Location :
Taipei
Print_ISBN :
978-1-4244-8095-1
Electronic_ISBN :
978-0-7695-4190-7
Type :
conf
DOI :
10.1109/ISPA.2010.8
Filename :
5634332
Link To Document :
بازگشت