Recent years have witnessed an increasing popularity of algorithm design for
distributed data, largely due to the fact that massive datasets are often
collected and stored in different locations. In the distributed setting
communication typically dominates the query processing time. Thus it becomes
crucial to design communication efficient algorithms for queries on distributed
data. Simultaneously, it has been widely recognized that partial optimizations,
where we are allowed to disregard a small part of the data, provide us
significantly better solutions. The motivation for disregarded points often
arise from noise and other phenomena that are pervasive in large data
scenarios.
In this paper we focus on partial clustering problems, $k$-center, $k$-median
and $k$-means, in the distributed model, and provide algorithms with
communication sublinear of the input size. As a consequence we develop the
first algorithms for the partial $k$-median and means objectives that run in
subquadratic running time. We also initiate the study of distributed algorithms
for clustering uncertain data, where each data point can possibly fall into
multiple locations under certain probability distribution.

提出了一种在分布式环境下运行的算法来解决部分聚类问题，包括 k 中心，k 中位数和 k 均值等，旨在提高通信效率和解决噪音和数据不确定性带来的影响。