DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2021.10

Fast Map Matching with Vertex-Monotone Fréchet Distance

Authors: Daniel Chen, Christian Sommer, and Daniel Wolleb

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

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.

Cite as

Daniel Chen, Christian Sommer, and Daniel Wolleb. Fast Map Matching with Vertex-Monotone Fréchet Distance. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/OASIcs.ATMOS.2021.10},
  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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2016.55

All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

Authors: Christian Sommer

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract

Given an undirected, unweighted graph G on n nodes, there is an O(n^2*poly log(n))-time algorithm that computes a data structure called distance oracle of size O(n^{5/3}*poly log(n)) answering approximate distance queries in constant time. For nodes at distance d the distance estimate is between d and 2d + 1. This new distance oracle improves upon the oracles of Patrascu and Roditty (FOCS 2010), Abraham and Gavoille (DISC 2011), and Agarwal and Brighten Godfrey (PODC 2013) in terms of preprocessing time, and upon the oracle of Baswana and Sen (SODA 2004) in terms of stretch. The running time analysis is tight (up to logarithmic factors) due to a recent lower bound of Abboud and Bodwin (STOC 2016). Techniques include dominating sets, sampling, balls, and spanners, and the main contribution lies in the way these techniques are combined. Perhaps the most interesting aspect from a technical point of view is the application of a spanner without incurring its constant additive stretch penalty.

Cite as

Christian Sommer. All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sommer:LIPIcs.ICALP.2016.55,
  author =	{Sommer, Christian},
  title =	{{All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.55},
  URN =		{urn:nbn:de:0030-drops-63354},
  doi =		{10.4230/LIPIcs.ICALP.2016.55},
  annote =	{Keywords: graph algorithms, data structures, approximate shortest paths, distance oracles, distance labels}
}

Search Results

Documents authored by Sommer, Christian

Fast Map Matching with Vertex-Monotone Fréchet Distance

Abstract

Cite as

All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

Abstract

Cite as

Thanks for your feedback!

Could not send message