Timezone: »

 
Poster
Distributed k-means and k-median clustering on general communication topologies
Maria-Florina F Balcan · Steven Ehrlich · Yingyu Liang

Sat Dec 07 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »
This paper provides new algorithms for distributed clustering for two popular center-based objectives, $k$-median and $k$-means. These algorithms have provable guarantees and improve communication complexity over existing approaches. Following a classic approach in clustering by \cite{har2004coresets}, we reduce the problem of finding a clustering with low cost to the problem of finding a `coreset' of small size. We provide a distributed method for constructing a global coreset which improves over the previous methods by reducing the communication complexity, and which works over general communication topologies. We provide experimental evidence for this approach on both synthetic and real data sets.
[ PDF] 

Author Information

Maria-Florina F Balcan (Georgia Tech)
Steven Ehrlich (Georgia Tech)
Yingyu Liang (Princeton University)

More from the Same Authors