Search Results

Documents authored by Conradi, Jacobus

Document
DOI: 10.4230/LIPIcs.SoCG.2024.42
Fast Approximations and Coresets for (k,𝓁)-Median Under Dynamic Time Warping

Authors: Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We present algorithms for the computation of ε-coresets for k-median clustering of point sequences in ℝ^d under the p-dynamic time warping (DTW) distance. Coresets under DTW have not been investigated before, and the analysis is not directly accessible to existing methods as DTW is not a metric. The three main ingredients that allow our construction of coresets are the adaptation of the ε-coreset framework of sensitivity sampling, bounds on the VC dimension of approximations to the range spaces of balls under DTW, and new approximation algorithms for the k-median problem under DTW. We achieve our results by investigating approximations of DTW that provide a trade-off between the provided accuracy and amenability to known techniques. In particular, we observe that given n curves under DTW, one can directly construct a metric that approximates DTW on this set, permitting the use of the wealth of results on metric spaces for clustering purposes. The resulting approximations are the first with polynomial running time and achieve a very similar approximation factor as state-of-the-art techniques. We apply our results to produce a practical algorithm approximating (k,𝓁)-median clustering under DTW.
Cite as

Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde. Fast Approximations and Coresets for (k,𝓁)-Median Under Dynamic Time Warping. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.SoCG.2024.42,
  author =	{Conradi, Jacobus and Kolbe, Benedikt and Psarros, Ioannis and Rohde, Dennis},
  title =	{{Fast Approximations and Coresets for (k,𝓁)-Median Under Dynamic Time Warping}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.42},
  URN =		{urn:nbn:de:0030-drops-199875},
  doi =		{10.4230/LIPIcs.SoCG.2024.42},
  annote =	{Keywords: Dynamic time warping, coreset, median clustering, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.28
Faster Approximate Covering of Subcurves Under the Fréchet Distance

Authors: Frederik Brüning, Jacobus Conradi, and Anne Driemel

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Subtrajectory clustering is an important variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number k of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given Δ to a representative curve. We focus on the case where the representative curves are line segments and approach this NP-hard problem with classical techniques from the area of geometric set cover: we use a variant of the multiplicative weights update method which was first suggested by Brönniman and Goodrich for set cover instances with small VC-dimension. We obtain a bicriteria-approximation algorithm that computes a set of O(klog(k)) line segments that cover a given polygonal curve of n vertices under Fréchet distance at most O(Δ). We show that the algorithm runs in Õ(k² n + k n³) time in expectation and uses Õ(k n + n³) space. For input curves that are c-packed and lie in the plane, we bound the expected running time by Õ(k² c² n) and the space by Õ(kn + c² n). In addition, we present a variant of the algorithm that uses implicit weight updates on the candidate set and thereby achieves near-linear running time in n without any assumptions on the input curve, while keeping the same approximation bounds. This comes at the expense of a small (polylogarithmic) dependency on the relative arclength.
Cite as

Frederik Brüning, Jacobus Conradi, and Anne Driemel. Faster Approximate Covering of Subcurves Under the Fréchet Distance. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bruning_et_al:LIPIcs.ESA.2022.28,
  author =	{Br\"{u}ning, Frederik and Conradi, Jacobus and Driemel, Anne},
  title =	{{Faster Approximate Covering of Subcurves Under the Fr\'{e}chet Distance}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.28},
  URN =		{urn:nbn:de:0030-drops-169660},
  doi =		{10.4230/LIPIcs.ESA.2022.28},
  annote =	{Keywords: Clustering, Set cover, Fr\'{e}chet distance, Approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.46
On Computing the k-Shortcut Fréchet Distance

Authors: Jacobus Conradi and Anne Driemel

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijections of the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterized version of this problem, where the number of shortcuts is bounded by a parameter k. The corresponding decision problem can be stated as follows: Given two polygonal curves T and B of at most n vertices, a parameter k and a distance threshold δ, is it possible to introduce k shortcuts along B such that the Fréchet distance of the resulting curve and the curve T is at most δ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (i) assuming the exponential-time-hypothesis (ETH), there exists no algorithm with running time bounded by n^o(k); (ii) there exists a decision algorithm with running time in O(k n^{2k+2} log n). In contrast, we also show that efficient approximate decider algorithms are possible, even when k is large. We present a (3+ε)-approximate decider algorithm with running time in O(k n² log² n) for fixed ε. In addition, we can show that, if k is a constant and the two curves are c-packed for some constant c, then the approximate decider algorithm runs in near-linear time.
Cite as

Jacobus Conradi and Anne Driemel. On Computing the k-Shortcut Fréchet Distance. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.ICALP.2022.46,
  author =	{Conradi, Jacobus and Driemel, Anne},
  title =	{{On Computing the k-Shortcut Fr\'{e}chet Distance}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.46},
  URN =		{urn:nbn:de:0030-drops-163875},
  doi =		{10.4230/LIPIcs.ICALP.2022.46},
  annote =	{Keywords: Fr\'{e}chet distance, Partial similarity, Conditional lower bounds, Approximation algorithms}
}
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 About DROPS Imprint Privacy Contact