Personal tools
You are here: Home CG seminar 2021 Static and streaming data structures for Fréchet distance queries
« December 2020 »
December
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Static and streaming data structures for Fréchet distance queries

Wednesday, December 9th, 16:10

underline

Omrit Filtser, SUNY Stony Brook

Abstract:

Measuring the similarity of two curves or trajectories is an important task that arises in various applications. The Fréchet distance and its variants became very popular in the last few decades, and some were successfully applied to real data sets. The Fréchet distance between two curves can be computed in quadratic time using a simple dynamic programming algorithm. However, under SETH, no strongly subquadratic algorithms exist, even if the solution may be approximated up to a factor of 3. Therefore, in applications where the curves in the given data set are large, a natural solution is to construct a data structure that allows fast distance queries.
In this talk I will discuss approximate distance oracles and nearest neighbour search data structures under the discrete Fréchet distance. In addition, I will present an algorithm that constructs simplifications in the streaming model, an oracle for distance queries to a sub-curve, and introduce the zoom-in problem.

Based on joint works with Arnold Filtser and Matya Katz.
 
Document Actions