2019/10/02 by Hossein Esfandiari, Vahab Mirrokni, Esfandiari, Hossein +3
Business, Management and Accounting · Computer Science · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Facility Location and Emergency Management #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1910.00788
openalex publication_date 2019/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Clustering of data points in metric space is among the most fundamental problems in computer science with plenty of applications in data mining, information retrieval and machine learning. Due to the necessity of clustering of large datasets, several streaming algorithms have been developed for different variants of clustering problems such as k-median and k-means problems. However, despite the importance of the context, the current understanding of balanced clustering (or more generally capacitated clustering) in the streaming setting is very limited. The only previously known streaming approximation algorithm for capacitated clustering requires three passes and only handles insertions. In this work, we develop the first single pass streaming algorithm for a general class of clustering problems that includes capacitated k-median and capacitated k-means in Euclidean space, using only poly( k d log Δ) space, where k is the number of clusters, d is the dimension and Δ is the maximum relative range of a coordinate. (Note that dlog Δ is the space required to represent one point.) This algorithm only violates the capacity constraint by a 1+ε factor. Interestingly, unlike the previous algorithm, our algorithm handles both insertions and deletions of points. To provide this result we define a decomposition of the space via some curved half-spaces. We used this decomposition to design a strong coreset of size poly( k d log Δ) for balanced clustering. Then, we show that this coreset is implementable in the streaming and distributed settings.