2026-08-15T09:23:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8251 2024-03-06T10:41:49Z ddc:004 open_access

Temporal Hierarchical Clustering Dey, Tamal K. Rossi, Alfred Sidiropoulos, Anastasios clustering hierarchical clustering multi-objective optimization dynamic metric spaces moving point sets approximation algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tamal K. Dey and Alfred Rossi and Anastasios Sidiropoulos 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.28 urn:nbn:de:0030-drops-82519 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.28 eng https://creativecommons.org/licenses/by/3.0/legalcode