• German

Main Navigation

Driemel/Krivosija/2018a: Probabilistic embeddings of the Fr\'echet distance

Bibtype Inproceedings
Bibkey Driemel/Krivosija/2018a
Author Driemel, Anne and Krivo\v{s}ija, Amer
Editor Epstein, Leah and Erlebach, Thomas
Title Probabilistic embeddings of the Fr\'echet distance
Booktitle Proceedings of the 16th International Workshop on Approximation and Online Algorithms (WAOA)
Series LNCS
Volume 11312
Pages 218-237
Publisher Springer
Abstract The Fr\'echet distance is a popular distance measure for curves which naturally lends itself to fundamental computational tasks, such as clustering, nearest-neighbor searching, and spherical range searching in the corresponding metric space. However, its inherent complexity poses considerable computational challenges in practice. To address this problem we study distortion of the probabilistic embedding that results from projecting the curves to a randomly chosen line. Such an embedding could be used in combination with, e.g. locality-sensitive hashing. We show that in the worst case and under reasonable assumptions, the discrete Fr\'echet distance between two polygonal curves of complexity $t$ in $\Re^d$, where $d\in\lbrace 2,3,4,5\rbrace$, degrades by a factor linear in $t$ with constant probability. We show upper and lower bounds on the distortion. We also evaluate our findings empirically on a benchmark data set. The preliminary experimental results stand in stark contrast with our lower bounds. They indicate that highly distorted projections happen very rarely in practice, and only for strongly conditioned input curves.

Keywords: Fr\'echet distance, Metric embeddings, Random projections.
Year 2018
Projekt SFB876-A2
Url https://doi.org/10.1007/978-3-030-04693-4\_14
Bibtex Here you can get this literature entry as BibTeX format.