Multi-Party Privacy-Preserving k-Means Clustering

Faculty Seminar given by Der-Tsai. Lee

DATE: October 12, 2010
PLACE: USI Università della Svizzera italiana, room SI-006, Informatics building (Via G. Buffi 13)
TIME: 16.30

ABSTRACT:
Given a finite set S of points in $\Re^m$, and integer k ≥ 1, the k -means clustering problem is to find k points (centers) so as to minimize the sum of the square of the Euclidean distance of each point in S to its closest cluster center.  We consider the classical k-means clustering problem with privacy consideration.  We assume that the data points are distributed in a certain manner among multiple parties and that when these parties collaboratively compute the k centers, they do not want to reveal any information about their own data.  In this talk we will give efficient parallel algorithms to address this problem under different data distribution models. (Joint work with Mr. Teng-Kai Yu and Shih-Ming Chang, National Taiwan University)

BIO:
Dr. Lee received his B.S. degree in Electrical Engineering from the National Taiwan University in 1971, and the M.S. and Ph. D. degrees in Computer Science from the University of Illinois at Urbana-Champaign in 1976 and 1978 respectively.
Dr. Lee has been with the Institute of Information Science, Academia Sinica, Taiwan, where he is a Distinguished Research Fellow since July 1, 1998. He was Director of the Institute of Information Science, Academia Sinica from 1998 to 2008. Prior to joining the Institute of Information Science, he was a Professor of the Department of Electrical Engineering and Computer Science, Northwestern University, where he has worked since 1978. He spent one year (August 1989 - August 1990) working as Program Director for Computer & Computation Theory Program, Division of Computer & Computation Research of the National Science Foundation.
Dr. Lee is also a Distinguished Research Chair Professor in the Dept. of Computer Science and Information Engineering, and the Graduate Institute of Electronics Engineering, National Taiwan University; Chair Professor of National Chiao-Tung University and National Chung-Hsing University.  He serves as Executive Director of the Taiwan Information Security Center (TWISC), Research Center for Information Technology Innovation, Academia Sinica, and Deputy Program Director of the Taiwan e-Learning and Digital Archives Program (TELDAP).
His research interests include design and analysis of algorithms, computational geometry, VLSI layout, web-based computing, algorithm visualization, software security, bio-informatics, and digital libraries.
He has published over 150 technical articles in scientific journals and conference proceedings. He is Editor of Algorithmica, ACM Journal on Computers and Cultural Heritage, LNCS Transactions on Computational Science, International J. of Information and Computer Security, Co-Chief Editor of Int'l Journal of Computational Geometry & Applications, and Series Editor of Lecture Notes Series on Computing for World Scientific Publishing Co., Singapore.
He is Fellow of IEEE, Fellow of ACM, elected Member of Academia Sinica, 2004, a recipient of Humboldt Research Award from the Alexander von Humboldt Foundation, Germany in 2007 and elected Member of the Academy of Sciences for the Developing World (TWAS) in 2008.

HOST: Prof. Evanthia Papadopoulou