Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
  Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben
Forschungspapier

A Fast Implementation of Near Neighbors Queries for Fréchet Distance (GIS Cup)

MPG-Autoren
/persons/resource/persons44182

Bringmann,  Karl       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:1803.00806.pdf
(Preprint), 157KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Baldus, J., & Bringmann, K. (2018). A Fast Implementation of Near Neighbors Queries for Fréchet Distance (GIS Cup). Retrieved from http://arxiv.org/abs/1803.00806.


Zitierlink: https://hdl.handle.net/21.11116/0000-0001-3E1A-E
Zusammenfassung
This paper describes an implementation of fast near-neighbours queries (also
known as range searching) with respect to the Fr\'echet distance. The algorithm
is designed to be efficient on practical data such as GPS trajectories. Our
approach is to use a quadtree data structure to enumerate all curves in the
database that have similar start and endpoints as the query curve. On these
curves we run positive and negative filters to narrow the set of potential
results. Only for those trajectories where these heuristics fail, we compute
the Fr\'echet distance exactly, by running a novel recursive variant of the
classic free-space diagram algorithm.
Our implementation won the ACM SIGSPATIAL GIS Cup 2017.