License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.34
URN: urn:nbn:de:0030-drops-78567
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7856/
Go to the corresponding LIPIcs Volume Portal

Dey, Tamal K. ; Rossi, Alfred ; Sidiropoulos, Anastasios

Temporal Clustering

pdf-format:
LIPIcs-ESA-2017-34.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{dey_et_al:LIPIcs:2017:7856,
  author =	{Tamal K. Dey and Alfred Rossi and Anastasios Sidiropoulos},
  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 =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7856},
  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}
}

Keywords: clustering, multi-objective optimization, dynamic metric spaces, moving point sets, approximation algorithms, hardness of approximation
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI