
D. Chen, A. Driemel, L. Guibas, A. Nguyen, and C. Wenk, Approximate Map Matching with respect to the Fréchet Distance, In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX '11).
Abstract:
We extend recent results using curve simplification for approximating the
Fr'{e}chet distance of realistic curves in near linear time to map matching:
the problem of matching a curve in an embedded graph. We show that the
theoretical bounds on the running time of the previous result still hold if only
one of the curves is simplified during the course of the approximation
algorithm. This enables our extension to the case of map matching under the
assumption that the graph is $phi$low density for a constant $phi$. We
present experimental evidence for this assumption and implement the extended
approximate matching algorithm. We show that it performs well on real world
data, such as GPS traces and road networks of urban areas. In particular, it is
able to perform matching tasks that took several hours with the exact matching
algorithm in under a second.
Bibtex:
@inproceedings{cdgnwammrfd11,
author = {Daniel Chen, Anne Driemel, Leonidas Guibas, Andy Nguyen, and Carola Wenk},
title = {Approximate Map Matching with respect to the Fréchet Distance},
booktitle = {Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (to appear)},
year = {2011}
}

