Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A fast implementation of near neighbors queries for Frechet distance (Bachelor thesis)
Speaker:Julian Baldus
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 28 November 2019
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Karl Bringmann, 11/06/2019 02:46 PM -- Created document.