Campus Event Calendar
Event Entry
What and Who
A fast implementation of near neighbors queries for Frechet distance (Bachelor thesis)
Julian Baldus
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 28 November 2019
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We present an algorithm for near neighbors queries with respect to Frechet distance that works well on real world inputs. It was the winning submission for the ACM SIGSPATIAL GIS Cup 2017 and a short paper has already been published.
For a data set with 20 000 polygonal curves with around 250 vertices each, we reach up to 1 000 queries per second.
To achieve this, we use a datastructure based on quadtrees and multiple upper and lower bounds to restrict the number of curves that have to be considered. We also describe a new recursive variant of the O(n^2) Frechet distance decision algorithm that is much faster in practice despite being slightly slower in the worst case.
Contact
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 11/06/2019 14:46 -- Created document.