Search Results

Documents authored by Höckendorff, Jan

Artifact
Software
DOI: 10.4230/artifacts.27658
Fréchet PCA

Authors: Anne Driemel, Jan Höckendorff, Ioannis Psarros, and Christian Sohler

Abstract
Cite as

Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler. Fréchet PCA (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27658,
   title = {{Fr\'{e}chet PCA}}, 
   author = {Driemel, Anne and H\"{o}ckendorff, Jan and Psarros, Ioannis and Sohler, Christian},
   note = {Software, DFG - 459420781 (https://gepris.dfg.de/project/459420781), swhId: \href{https://archive.softwareheritage.org/swh:1:dir:42897eeb29e82508265e89725746120e29ec7177;origin=https://github.com/jahoec/PCA-on-Curves;visit=swh:1:snp:add0b960d51507d2335bfae0ac1d119fee546790;anchor=swh:1:rev:b9364ffbd457f0f3be324043c41b4a856355febd}{\texttt{swh:1:dir:42897eeb29e82508265e89725746120e29ec7177}} (visited on 2026-08-25)},
   url = {https://github.com/jahoec/PCA-on-Curves},
   doi = {10.4230/artifacts.27658},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.96
Time Series Decomposition Using the Fréchet Distance

Authors: Anne Driemel, Jan Höckendorff, Ioannis Psarros, and Christian Sohler

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of k base curves of length at most l such that the sum of Fréchet distances of the time series to a "Fréchet combination" of the base curves is minimized. Here, a Fréchet combination allows to combine individually scaled base curves using a k-dimensional traversal. We call the problem of finding a set of optimal base curves the Fréchet decomposition problem and we consider two variants: (a) the base curves can be arbitrary curves of bounded length and (b) the curves come from a given finite set of candidate curves. We think of the Fréchet decomposition problem as a Fréchet variant of principal component analysis. For the case of a single base curve we develop a (1+ε)-approximation algorithm for the Fréchet decomposition problem. Additionally we give an exact algorithm for the projection distance problem that asks to compute the distance of one given time series to a given set of k base curves. This allows us to design an exact algorithm for the Fréchet decomposition problem for general k when curves come from a fixed candidate set.
Cite as

Anne Driemel, Jan Höckendorff, Ioannis Psarros, and Christian Sohler. Time Series Decomposition Using the Fréchet Distance. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 96:1-96:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{driemel_et_al:LIPIcs.ESA.2026.96,
  author =	{Driemel, Anne and H\"{o}ckendorff, Jan and Psarros, Ioannis and Sohler, Christian},
  title =	{{Time Series Decomposition Using the Fr\'{e}chet Distance}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{96:1--96:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.96},
  URN =		{urn:nbn:de:0030-drops-272322},
  doi =		{10.4230/LIPIcs.ESA.2026.96},
  annote =	{Keywords: Time Series Analysis, Fr\'{e}chet Distance, Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.80
Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics

Authors: Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, and Di Yue

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
In the metric k-median problem we are given a finite metric space (X∪ Y, 𝐝) and the objective is to compute a set of k centers C ⊆ Y that minimizes ∑_{p ∈ X} min_{c ∈ C} 𝐝(p,c). In general metric spaces, the best polynomial time algorithm, which is due to Cohen-Addad, Grandoni, Lee, Schwiegelshohn, and Svensson [Vincent Cohen-Addad et al., 2025], computes a (2+ε)-approximation for arbitrary constant ε > 0. However, if the metric space has bounded doubling dimension, a near linear time (1+ε)-approximation algorithm is known due to the work of Cohen-Addad, Feldmann, and Saulpic [Vincent Cohen{-}Addad et al., 2021]. In this paper, we show that the (1+ε)-approximation algorithm can be generalized to the case when either X or Y has bounded doubling dimension (but the other set not). The case when X has bounded doubling dimension is motivated by the assumption that even though X is part of a high-dimensional space, it may be that it is close to a low-dimensional structure. The case when Y has bounded doubling dimension is perhaps more natural. It is motivated by specific clustering problems where the centers are low-dimensional. Specifically, our work in this setting implies the first near linear time approximation algorithm for the (k,𝓁)-median problem under discrete Fréchet distance when 𝓁 is constant. The latter problem is a version of the k-median problem under Fréchet distance when the input consists of time series of z reals and where the centers are time series of 𝓁 reals [Anne Driemel et al., 2016]. Previously, for this problem no (1+ε)-approximation algorithm with running time polynomial in k was known. We also introduce a novel complexity reduction for time series of real values that leads to a similar result for the case of discrete Fréchet distance. In order to solve the case when Y has a bounded doubling dimension, we introduce a form of dimension reduction that replaces points from X by sets of points in Y. To solve the case when X has a bounded doubling dimension, we generalize Talwar’s decomposition [Kunal Talwar, 2004] of doubling metrics to our setting. The running time of our algorithms is 2^{2^t} Õ(n+m) where t = O(ddim log ddim/ε) and where ddim is the doubling dimension of X (resp. Y). The results also extend to the metric (uncapacitated) facility location problem. We believe that our techniques are likely applicable to other problems.
Cite as

Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, and Di Yue. Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{driemel_et_al:LIPIcs.ICALP.2026.80,
  author =	{Driemel, Anne and H\"{o}ckendorff, Jan and Psarros, Ioannis and Sohler, Christian and Yue, Di},
  title =	{{Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.80},
  URN =		{urn:nbn:de:0030-drops-264693},
  doi =		{10.4230/LIPIcs.ICALP.2026.80},
  annote =	{Keywords: Approximation Algorithms, Doubling Spaces, Facility Location, k-Median, Discrete Fr\'{e}chet Distance}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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