DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.28

Temporal Hierarchical Clustering

Authors: Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

We study hierarchical clusterings of metric spaces that change over time. This is a natural geo- metric primitive for the analysis of dynamic data sets. Specifically, we introduce and study the problem of finding a temporally coherent sequence of hierarchical clusterings from a sequence of unlabeled point sets. We encode the clustering objective by embedding each point set into an ultrametric space, which naturally induces a hierarchical clustering of the set of points. We enforce temporal coherence among the embeddings by finding correspondences between successive pairs of ultrametric spaces which exhibit small distortion in the Gromov-Hausdorff sense. We present both upper and lower bounds on the approximability of the resulting optimization problems.

Cite as

Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos. Temporal Hierarchical Clustering. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ISAAC.2017.28,
  author =	{Dey, Tamal K. and Rossi, Alfred and Sidiropoulos, Anastasios},
  title =	{{Temporal Hierarchical Clustering}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.28},
  URN =		{urn:nbn:de:0030-drops-82519},
  doi =		{10.4230/LIPIcs.ISAAC.2017.28},
  annote =	{Keywords: clustering, hierarchical clustering, multi-objective optimization, dynamic metric spaces, moving point sets, approximation algorithms}
}

Document

DOI: 10.4230/LIPIcs.ESA.2017.34

Temporal Clustering

Authors: Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We study the problem of clustering sequences of unlabeled point sets taken from a common metric space. Such scenarios arise naturally in applications where a system or process is observed in distinct time intervals, such as biological surveys and contagious disease surveillance. In this more general setting existing algorithms for classical (i.e. static) clustering problems are not applicable anymore. We propose a set of optimization problems which we collectively refer to as temporal clustering. The quality of a solution to a temporal clustering instance can be quantified using three parameters: the number of clusters k, the spatial clustering cost r, and the maximum cluster displacement delta between consecutive time steps. We consider spatial clustering costs which generalize the well-studied k-center, discrete k-median, and discrete k-means objectives of classical clustering problems. We develop new algorithms that achieve trade-offs between the three objectives k, r, and delta. Our upper bounds are complemented by inapproximability results.

Cite as

Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos. Temporal Clustering. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2017.34,
  author =	{Dey, Tamal K. and Rossi, Alfred and Sidiropoulos, Anastasios},
  title =	{{Temporal Clustering}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.34},
  URN =		{urn:nbn:de:0030-drops-78567},
  doi =		{10.4230/LIPIcs.ESA.2017.34},
  annote =	{Keywords: clustering, multi-objective optimization, dynamic metric spaces, moving point sets, approximation algorithms, hardness of approximation}
}

Search Results

Documents authored by Rossi, Alfred

Temporal Hierarchical Clustering

Abstract

Cite as

Temporal Clustering

Abstract

Cite as

Thanks for your feedback!

Could not send message