Massively parallel and streaming algorithms for balanced clustering

Clustering is a fundamental problem with a wide range of applications. In this paper, we study a balanced version of the well-known k -center clustering problem, where the objective is to select k centers from a given set of points, and assign to each center at most L of the input points, so as to minimize the maximum distance from a point to the center to which it is assigned. We assume soft capacities, where points are allowed to be selected as center more than once. Motivated by applications involving massive datasets, we study the problem in the massively parallel computation (MPC) and streaming models. In particular, we present a two-round MPC algorithm for the balanced k -center problem, achieving an approximation factor of 5 (cid:11) + 2, where (cid:11) is the approximation factor of the corresponding sequential algorithm. This substantially improves the currently best approximation factor of 32 (cid:11) , available for the problem. We show that the approximation factor of our algorithm can be further improved to 5 + " in all spaces with bounded doubling dimension, including the Euclidean space. We also consider the balanced k -center problem in the streaming model, and present a constant-factor streaming algorithm in any metric space using O ( kn " ) memory, and a factor 5 + " streaming algorithm using O ( k polylog n ) memory in doubling metrics.

• Publication year

  2023

• Venue

  Theoretical Computer Science

• Publication date

  2023-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.tcs.2023.114296
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Fair k-Center Clustering in MapReduce and Streaming Settings

  2022cited by this paper
• Extreme k-Center Clustering

  2021cited by this paper
• Data stream clustering: a review

  2020cited by this paper
• Improved Algorithms for Distributed Balanced Clustering

  2020cited by this paper
• Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially

  2018influential reference
• Communication Steps for Parallel Query Processing

  2017cited by this paper
• Efficient Parallel Algorithms for k-Center Clustering

  2016cited by this paper
• Fast Distributed k-Center Clustering with Outliers on Massive Data

  2015cited by this paper
• A survey on data stream clustering and classification

  2015cited by this paper
• Composable core-sets for diversity and coverage maximization

  2014cited by this paper
• Distributed Balanced Clustering via Mapping Coresets

  2014cited by this paper
• Centrality of trees for capacitated k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-center

  2014cited by this paper
• Data stream clustering: A survey

  2013cited by this paper
• Centrality of Trees for Capacitated k-Center

  2013cited by this paper
• LP Rounding for k-Centers with Non-uniform Hard Capacities

  2012cited by this paper
• Fast clustering using MapReduce

  2011cited by this paper
• A model of computation for MapReduce

  2010cited by this paper
• Tight results for clustering and summarizing data streams

  2009cited by this paper
• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity

  2008cited by this paper
• Data streams: algorithms and applications

  2005cited by this paper
• The Capacitated K-Center Problem

  2000influential reference
• Incremental clustering and dynamic information retrieval

  1997cited by this paper
• How to Allocate Network Centers

  1993cited by this paper
• A Best Possible Heuristic for the k-Center Problem

  1985cited by this paper
• Clustering to Minimize the Maximum Intercluster Distance

  1985cited by this paper
• Decomposable Searching Problems I: Static-to-Dynamic Transformation

  1980cited by this paper

• No citing papers are available for this paper.