Personal tools
You are here: Home CG seminar 2021 Static and streaming data structures for Fréchet distance queries
« January 2022 »
Log in

Forgot your password?

Static and streaming data structures for Fréchet distance queries

Wednesday, December 9th, 16:10


Omrit Filtser, SUNY Stony Brook


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