Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially.

Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftKonferenceartikelForskningpeer review

Abstract

Center-based clustering is a fundamental primitive for data analysis and becomes very challenging for large datasets. In this paper, we focus on the popular k-center variant which, given a set S of points from some metric space and a parameter k < |S|, requires to identify a subset of k centers in S minimizing the maximum distance of any point of S from its closest center. A more general formulation, introduced to deal with noisy datasets, features a further parameter z and allows up to z points of S (outliers) to be disregarded when computing the maximum distance from the centers. We present coreset-based 2-round MapReduce algorithms for the above two formulations of the problem, and a 1-pass Streaming algorithm for the case with outliers. For any fixed &#1013; > 0, the algorithms yield solutions whose approximation ratios are a mere additive term &#1013; away from those achievable by the best known polynomial-time sequential algorithms, a result that substantially improves upon the state of the art. Our algorithms are rather simple and adapt to the intrinsic complexity of the dataset, captured by the doubling dimension D of the metric space. Specifically, our analysis shows that the algorithms become very space-efficient for the important case of small (constant) D. These theoretical results are complemented with a set of experiments on real-world and synthetic datasets of up to over a billion points, which show that our algorithms yield better quality solutions over the state of the art while featuring excellent scalability, and that they also lend themselves to sequential implementations much faster than existing ones
OriginalsprogEngelsk
TidsskriftProceedings of the VLDB Endowment
Vol/bind12
ISSN2150-8097
DOI
StatusUdgivet - 2019

Emneord

  • k-center clustering
  • large datasets
  • coreset
  • MapReduce algorithms
  • streaming algorithms

Fingeraftryk

Dyk ned i forskningsemnerne om 'Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially.'. Sammen danner de et unikt fingeraftryk.

Citationsformater