1 Search Results for "Rohde, Dennis"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.53
Random Projections for Curves in High Dimensions

Authors: Ioannis Psarros and Dennis Rohde

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Modern time series analysis requires the ability to handle datasets that are inherently high-dimensional; examples include applications in climatology, where measurements from numerous sensors must be taken into account, or inventory tracking of large shops, where the dimension is defined by the number of tracked items. The standard way to mitigate computational issues arising from the high dimensionality of the data is by applying some dimension reduction technique that preserves the structural properties of the ambient space. The dissimilarity between two time series is often measured by "discrete" notions of distance, e.g. the dynamic time warping or the discrete Fréchet distance. Since all these distance functions are computed directly on the points of a time series, they are sensitive to different sampling rates or gaps. The continuous Fréchet distance offers a popular alternative which aims to alleviate this by taking into account all points on the polygonal curve obtained by linearly interpolating between any two consecutive points in a sequence. We study the ability of random projections à la Johnson and Lindenstrauss to preserve the continuous Fréchet distance of polygonal curves by effectively reducing the dimension. In particular, we show that one can reduce the dimension to O(ε^{-2} log N), where N is the total number of input points while preserving the continuous Fréchet distance between any two determined polygonal curves within a factor of 1± ε. We conclude with applications on clustering.
Cite as

Ioannis Psarros and Dennis Rohde. Random Projections for Curves in High Dimensions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 53:1-53:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{psarros_et_al:LIPIcs.SoCG.2023.53,
  author =	{Psarros, Ioannis and Rohde, Dennis},
  title =	{{Random Projections for Curves in High Dimensions}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.53},
  URN =		{urn:nbn:de:0030-drops-179030},
  doi =		{10.4230/LIPIcs.SoCG.2023.53},
  annote =	{Keywords: polygonal curves, time series, dimension reduction, Johnson-Lindenstrauss lemma, Fr\'{e}chet distance}
}
  • Refine by Author
  • 1 Psarros, Ioannis
  • 1 Rohde, Dennis

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Random projections and metric embeddings

  • Refine by Keyword
  • 1 Fréchet distance
  • 1 Johnson-Lindenstrauss lemma
  • 1 dimension reduction
  • 1 polygonal curves
  • 1 time series

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact