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

Baldus, Julian; Bringmann, Karl

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

このアイテムの新しいバージョンが利用可能です:
https://pure.mpg.de/pubman/item/item_2584993_3

詳細要約

公開

成果報告書

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

MPS-Authors

/persons/resource/persons44182

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

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:1803.00806.pdf
(プレプリント), 157KB

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/21.11116/0000-0001-3E1A-E

要旨

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.