License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.53
URN: urn:nbn:de:0030-drops-179030
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17903/
Go to the corresponding LIPIcs Volume Portal

Psarros, Ioannis ; Rohde, Dennis

Random Projections for Curves in High Dimensions

pdf-format:
LIPIcs-SoCG-2023-53.pdf (0.7 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2023/17903},
  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}
}

Keywords: polygonal curves, time series, dimension reduction, Johnson-Lindenstrauss lemma, Fréchet distance
Collection: 39th International Symposium on Computational Geometry (SoCG 2023)
Issue Date: 2023
Date of publication: 09.06.2023

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