Massively Parallel and Dynamic Algorithms for Minimum Size Clustering

Clustering of data in metric spaces is a fundamental problem and has many applications in data mining and it is often used as an unsupervised learning tool inside other machine learning systems. In many scenarios where we are concerned with the privacy implications of clustering users, clusters are required to have minimum-size constraint. A canonical example of min-size clustering is in enforcing anonymization and the protection of the privacy of user data. Our work is motivated by real-world applications (such as the Federated Learning of Cohorts project–FLoC) where a min size clustering algorithm needs to handle very large amount of data and the data may also change over time. Thus efficient parallel or dynamic algorithms are desired. In this paper, we study the r-gather problem, a natural formulation of minimum-size clustering in metric spaces. The goal of r-gather is to partition n points into clusters such that each cluster has size at least r, and the maximum radius of the clusters is minimized. This additional constraint completely changes the algorithmic nature of the problem, and many clustering techniques fail. Also previous dynamic and parallel algorithms do not achieve desirable complexity. We propose algorithms both in the Massively Parallel Computation (MPC) model and in the dynamic setting. Our MPC algorithm handles input points from the Euclidean space ℝd. It computes an O(1)-approximate solution of r-gather in O(log∊ n) rounds using total space O(n1 + γ · d) for arbitrarily small constants ∊, γ > 0. In addition our algorithm is fully scalable, i.e., there is no lower bound on the memory per machine. Our dynamic algorithm maintains an O(1)-approximate r-gather solution under insertions/deletions of points in a metric space with doubling dimension d. The update time is r·2O(d)·logO(1) Λ and the query time is 2O(d) · logO(1) Λ, where Λ is the ratio between the largest and the smallest distance. To obtain our results, we reveal connections between r-gather and r-nearest neighbors and provide several geometric and graph algorithmic tools including a near neighbor graph construction, and results on the maximal independent set / ruling set of the power graph in the MPC model, which might be both of independent interest. To show their generality, we extend our algorithm to solve several variants of r-gather in the MPC model, including r-gather with outliers and r-gather with total distance cost. Finally, we show effectiveness of these algorithmic techniques via a preliminary empirical study for Interest-Based Advertisement applications.