Probabilistic embeddings of the Fréchet distance

Anne Driemel, Amer Krivošija

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The Fréchet 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échet distance between two polygonal curves of complexity t in ℝ d , where d ∈ {2, 3, 4, 5}, 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.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers
EditorsLeah Epstein, Thomas Erlebach
Place of PublicationCham
PublisherSpringer
Pages218-237
Number of pages20
ISBN (Electronic)978-3-030-04693-4
ISBN (Print)978-3-030-04692-7
DOIs
Publication statusPublished - 29 Nov 2018
Event16th Workshop on Approximation and Online Algorithms, WAOA 2018 - Helsinki, Finland
Duration: 23 Aug 201824 Aug 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11312 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th Workshop on Approximation and Online Algorithms, WAOA 2018
CountryFinland
CityHelsinki
Period23/08/1824/08/18

Keywords

  • Fréchet distance
  • Metric embeddings
  • Random projections

Fingerprint Dive into the research topics of 'Probabilistic embeddings of the Fréchet distance'. Together they form a unique fingerprint.

  • Cite this

    Driemel, A., & Krivošija, A. (2018). Probabilistic embeddings of the Fréchet distance. In L. Epstein, & T. Erlebach (Eds.), Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers (pp. 218-237). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11312 LNCS). Cham: Springer. https://doi.org/10.1007/978-3-030-04693-4_14