Extreme k-Center Clustering

Authors

  • MohammadHossein Bateni Google Research
  • Hossein Esfandiari Google Research
  • Manuela Fischer ETH Zurich
  • Vahab Mirrokni Google Research

Keywords:

Scalability, Parallel & Distributed Systems, Clustering

Abstract

Metric clustering is a fundamental primitive in machine learning with several applications for mining massive datasets. An important example of metric clustering is the k-center problem. While this problem has been extensively studied in distributed settings, all previous algorithms use Ω(k) space per machine and Ω(n k) total work. In this paper, we develop the first highly scalable approximation algorithm for k-center clustering, with O~(n^ε) space per machine and O~(n^(1+ε)) total work, for arbitrary small constant ε. It produces an O(log log log n)-approximate solution with k(1+o(1)) centers in O(log log n) rounds of computation.

Downloads

Published

2021-05-18

How to Cite

Bateni, M., Esfandiari, H., Fischer, M., & Mirrokni, V. (2021). Extreme k-Center Clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 3941-3949. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16513

Issue

Section

AAAI Technical Track on Data Mining and Knowledge Management