1 Search Results for "Mazzetto, Alessio"

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.34
Accurate MapReduce Algorithms for k-Median and k-Means in General Metric Spaces

Authors: Alessio Mazzetto, Andrea Pietracaprina, and Geppino Pucci

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

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-median and k-means variants which, given a set P of points from a metric space and a parameter k<|P|, require to identify a set S of k centers minimizing, respectively, the sum of the distances and of the squared distances of all points in P from their closest centers. Our specific focus is on general metric spaces, for which it is reasonable to require that the centers belong to the input set (i.e., S subseteq P). We present coreset-based 3-round distributed approximation algorithms for the above problems using the MapReduce computational model. The algorithms are rather simple and obliviously adapt to the intrinsic complexity of the dataset, captured by the doubling dimension D of the metric space. Remarkably, the algorithms attain approximation ratios that can be made arbitrarily close to those achievable by the best known polynomial-time sequential approximations, and they are very space efficient for small D, requiring local memory sizes substantially sublinear in the input size. To the best of our knowledge, no previous distributed approaches were able to attain similar quality-performance guarantees in general metric spaces.
Cite as

Alessio Mazzetto, Andrea Pietracaprina, and Geppino Pucci. Accurate MapReduce Algorithms for k-Median and k-Means in General Metric Spaces. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mazzetto_et_al:LIPIcs.ISAAC.2019.34,
  author =	{Mazzetto, Alessio and Pietracaprina, Andrea and Pucci, Geppino},
  title =	{{Accurate MapReduce Algorithms for k-Median and k-Means in General Metric Spaces}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.34},
  URN =		{urn:nbn:de:0030-drops-115302},
  doi =		{10.4230/LIPIcs.ISAAC.2019.34},
  annote =	{Keywords: Clustering, k-median, k-means, MapReduce, Coreset}
}
  • Refine by Author
  • 1 Mazzetto, Alessio
  • 1 Pietracaprina, Andrea
  • 1 Pucci, Geppino

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → MapReduce algorithms

  • Refine by Keyword
  • 1 Clustering
  • 1 Coreset
  • 1 MapReduce
  • 1 k-means
  • 1 k-median

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact