License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2021.10
URN: urn:nbn:de:0030-drops-148794
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14879/
Go to the corresponding OASIcs Volume Portal

Chen, Daniel ; Sommer, Christian ; Wolleb, Daniel

Fast Map Matching with Vertex-Monotone Fréchet Distance

pdf-format:
OASIcs-ATMOS-2021-10.pdf (4 MB)

Abstract

We study a generalization for map matching algorithms that includes both geometric approaches such as the Fréchet distance and global weight approaches such as those typically used by Hidden Markov Models. Through this perspective, we discovered an efficient map matching algorithm with respect to the vertex-monotone Fréchet distance while using a heuristic tie-breaker inspired by global weight methods. While the classical Fréchet distance requires parameterizations to be monotone, the vertex-monotone Fréchet distance allows backtracking within edges. Our analysis and experimental evaluations show that relaxing the monotonicity constraint enables significantly faster algorithms without significantly altering the resulting map matched paths.

BibTeX - Entry

@InProceedings{chen_et_al:OASIcs.ATMOS.2021.10,
  author =	{Chen, Daniel and Sommer, Christian and Wolleb, Daniel},
  title =	{{Fast Map Matching with Vertex-Monotone Fr\'{e}chet Distance}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{10:1--10:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14879},
  URN =		{urn:nbn:de:0030-drops-148794},
  doi =		{10.4230/OASIcs.ATMOS.2021.10},
  annote =	{Keywords: Fr\'{e}chet distance, map matching, minimum bottleneck path}
}

Keywords: Fréchet distance, map matching, minimum bottleneck path
Collection: 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Issue Date: 2021
Date of publication: 27.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI