TY - GEN
T1 - Probabilistic embeddings of the Fréchet distance
AU - Driemel, Anne
AU - Krivošija, Amer
PY - 2018/11/29
Y1 - 2018/11/29
N2 -
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.
AB -
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.
KW - Fréchet distance
KW - Metric embeddings
KW - Random projections
UR - http://www.scopus.com/inward/record.url?scp=85058481970&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-04693-4_14
DO - 10.1007/978-3-030-04693-4_14
M3 - Conference contribution
AN - SCOPUS:85058481970
SN - 978-3-030-04692-7
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 218
EP - 237
BT - Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers
A2 - Epstein, Leah
A2 - Erlebach, Thomas
PB - Springer
CY - Cham
T2 - 16th Workshop on Approximation and Online Algorithms, WAOA 2018
Y2 - 23 August 2018 through 24 August 2018
ER -