Non-uniform data distribution for communication-efficient parallel clustering

► We present a communication-efficient parallel formulation for the k-means clustering algorithm based on KD-trees. ► The algorithm does not require global communication and can dynamically select subsets of processes for group communication. ► The algorithm can provide the exact deterministic solution of an equivalent sequential k-means algorithm, i.e., run over the aggregated data. ► The method can also improve its communication efficiency further by approximating the centralised k-means algorithm as closely as desired.