Fast Map Matching with Vertex-Monotone Frechet Distance

Daniel Chen, Christian Sommer, and Daniel Wolleb
ATMOS 2021 - 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (pp. 10:1--10:20)

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.

@inproceedings{CSW21,
 author    = {Daniel Chen and
              Christian Sommer and
              Daniel Wolleb},
 title     = {Fast Map Matching with Vertex-Monotone Frechet Distance},
 year      = {2021},
 booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling,
              Optimization, and Systems (ATMOS 2021)},
 pages     = {10:1--10:20},
 doi       = {10.4230/OASIcs.ATMOS.2021.10}
}

Official version
Local version (3.8 MB)

Home → Publications → Fast Map Matching with Vertex-Monotone Frechet Distance