Timezone: »

Distributed $k$-Clustering for Data with Heavy Noise
Shi Li · Xiangyu Guo

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 210 #73
In this paper, we consider the $k$-center/median/means clustering with outliers problems (or the $(k, z)$-center/median/means problems) in the distributed setting. Most previous distributed algorithms have their communication costs linearly depending on $z$, the number of outliers. Recently Guha et al.[10] overcame this dependence issue by considering bi-criteria approximation algorithms that output solutions with $2z$ outliers. For the case where $z$ is large, the extra $z$ outliers discarded by the algorithms might be too large, considering that the data gathering process might be costly. In this paper, we improve the number of outliers to the best possible $(1+\epsilon)z$, while maintaining the $O(1)$-approximation ratio and independence of communication cost on $z$. The problems we consider include the $(k, z)$-center problem, and $(k, z)$-median/means problems in Euclidean metrics. Implementation of the our algorithm for $(k, z)$-center shows that it outperforms many previous algorithms, both in terms of the communication cost and quality of the output solution.

Author Information

Shi Li (University at Buffalo)
Xiangyu Guo (State University of New York at Buffalo)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors