Document Open Access Logo

Fast Map Matching with Vertex-Monotone Fréchet Distance

Authors Daniel Chen, Christian Sommer, Daniel Wolleb

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.10.pdf
  • Filesize: 3.8 MB
  • 20 pages

Document Identifiers

Author Details

Daniel Chen
  • Apple, Cupertino, CA, USA
Christian Sommer
  • Apple, Cupertino, CA, USA
Daniel Wolleb
  • Apple, Cupertino, CA, USA

Cite As Get BibTex

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) https://doi.org/10.4230/OASIcs.ATMOS.2021.10

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
Keywords
  • Fréchet distance
  • map matching
  • minimum bottleneck path

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K Agarwal, Sariel Har-Peled, Nabil H Mustafa, and Yusu Wang. Near-linear time approximation algorithms for curve simplification. Algorithmica, 42(3-4):203-219, 2005. Google Scholar
  2. Mahmuda Ahmed, Sophia Karagiorgou, Dieter Pfoser, and Carola Wenk. A comparison and evaluation of map construction algorithms using vehicle tracking data. GeoInformatica, 19(3):601-632, 2015. Google Scholar
  3. Mohamed Ali, John Krumm, Travis Rautman, and Ankur Teredesai. ACM SIGSPATIAL GIS cup 2012. In 20th International Conference on Advances in Geographic Information Systems, SIGSPATIAL'12, pages 597-600, 2012. Google Scholar
  4. Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk. Matching planar maps. J. Algorithms, 49(2):262-283, 2003. Announced at SODA'03. Google Scholar
  5. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, 5:75-91, 1995. Google Scholar
  6. Javed A. Aslam, Sejoon Lim, Xinghao Pan, and Daniela Rus. City-scale traffic estimation from a roving sensor network. In 10th ACM Conference on Embedded Network Sensor Systems, SenSys'12, pages 141-154. ACM, 2012. Google Scholar
  7. Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In 31st International Conference on Very Large Data Bases, VLDB'05, pages 853-864. ACM, 2005. Google Scholar
  8. Lili Cao and John Krumm. From GPS traces to a routable road map. In 17th International Symposium on Advances in Geographic Information Systems, SIGSPATIAL'09, pages 3-12. ACM, 2009. Google Scholar
  9. Pablo Samuel Castro, Daqing Zhang, and Shijian Li. Urban traffic modelling and prediction using large scale taxi GPS traces. In 10th International Conference on Pervasive Computing, Pervasive'12, volume 7319 of Lecture Notes in Computer Science, pages 57-72. Springer, 2012. Google Scholar
  10. Erin W. Chambers, Brittany Terese Fasy, Yusu Wang, and Carola Wenk. Map-matching using shortest paths. ACM Transactions on Spatial Algorithms and Systems, 6(1):6:1-6:17, 2020. Google Scholar
  11. Daniel Chen, Anne Driemel, Leonidas J. Guibas, Andy Nguyen, and Carola Wenk. Approximate map matching with respect to the Fréchet distance. In 14th Workshop on Algorithm Engineering and Experiments, ALENEX'11, pages 75-83, 2011. Google Scholar
  12. Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. Customizable route planning in road networks. Transportation Science, 51(2):566-591, 2017. Google Scholar
  13. Daniel Delling, Dennis Schieferdecker, and Christian Sommer. Traffic-aware routing in road networks. In 34th IEEE International Conference on Data Engineering, ICDE'18, pages 1543-1548, 2018. Google Scholar
  14. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Customizable contraction hierarchies. ACM J. Exp. Algorithmics, 21(1):1.5:1-1.5:49, 2016. Google Scholar
  15. Julian Dibbelt, Ben Strasser, and Dorothea Wagner. RoutingKit. https://github.com/RoutingKit/RoutingKit, 2020.
  16. Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, 1959. Google Scholar
  17. David H Douglas and Thomas K Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: the international journal for geographic information and geovisualization, 10(2):112-122, 1973. Google Scholar
  18. Gregory D. Erhardt, Sneha Roy, Drew Cooper, Bhargava Sana, Mei Chen, and Joe Castiglione. Do transportation network companies decrease or increase congestion? Science Advances, 5(5), 2019. Google Scholar
  19. Nivan Ferreira, Jorge Poco, Huy T. Vo, Juliana Freire, and Cláudio T. Silva. Visual exploration of big spatio-temporal urban data: A study of new york city taxi trips. IEEE Transactions on Visualization and Computer Graphics, 19(12):2149-2158, 2013. Google Scholar
  20. M Maurice Fréchet. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo (1884-1940), 22(1):1-72, 1906. Google Scholar
  21. Stefan Funke, Tobias Rupp, André Nusser, and Sabine Storandt. PATHFINDER: storage and indexing of massive trajectory sets. In 16th International Symposium on Spatial and Temporal Databases, SSTD'19, pages 90-99. ACM, 2019. Google Scholar
  22. Geofabrik GmbH. Geofabrik OSM NorCal map. https://download.geofabrik.de/north-america/us/california/norcal.html, 2020.
  23. Chong Yang Goh, Justin Dauwels, Nikola Mitrovic, Muhammad Tayyab Asif, Ali Oran, and Patrick Jaillet. Online map-matching based on hidden Markov model for real-time traffic sensing applications. In 15th International IEEE Conference on Intelligent Transportation Systems, ITSC'12, pages 776-781, 2012. Google Scholar
  24. GraphHopper. Map matching based on graphhopper. https://github.com/graphhopper/map-matching, 2020.
  25. Songtao He, Favyen Bastani, Sofiane Abbar, Mohammad Alizadeh, Hari Balakrishnan, Sanjay Chawla, and Sam Madden. Roadrunner: improving the precision of road network inference from GPS trajectories. In 26th International Conference on Advances in Geographic Information Systems, SIGSPATIAL'18, pages 3-12. ACM, 2018. Google Scholar
  26. Abdeltawab M. Hendawi, Sree Sindhu Sabbineni, Jianwei Shen, Yaxiao Song, Peiwei Cao, Zhihong Zhang, John Krumm, and Mohamed H. Ali. Which one is correct, the map or the GPS trace. In 27th International Conference on Advances in Geographic Information Systems, SIGSPATIAL'19, pages 472-475. ACM, 2019. Google Scholar
  27. Roel Jacobs. Constructing maps by clustering trajectories. Master’s thesis, TU Eindhoven, 2016. Google Scholar
  28. Erik Jenelius and Haris N. Koutsopoulos. Travel time estimation for urban road networks using low frequency probe vehicle data. Transportation Research Part B: Methodological, 53:64-81, 2013. Google Scholar
  29. JOSM. An extensible editor for openstreetmap. https://josm.openstreetmap.de, 2020.
  30. Benjamin B. Krogh, Christian S. Jensen, and Kristian Torp. Efficient in-memory indexing of network-constrained trajectories. In 24th ACM International Conference on Advances in Geographic Information Systems SIGSPATIAL'16, pages 17:1-17:10. ACM, 2016. Google Scholar
  31. Yang Li, Qixing Huang, Michael Kerber, Lin Zhang, and Leonidas J. Guibas. Large-scale joint map matching of GPS traces. In 21st International Conference on Advances in Geographic Information Systems, SIGSPATIAL'13, pages 214-223. ACM, 2013. Google Scholar
  32. Paul Newson and John Krumm. Hidden Markov map matching through noise and sparseness. In 17th ACM International Symposium on Advances in Geographic Information Systems, SIGSPATIAL'09, pages 336-343. ACM, 2009. Google Scholar
  33. Gustavo Niemeyer. geohash.org is public! https://web.archive.org/web/20080305223755/http://blog.labix.org/#post-85, 2008.
  34. Patrick Niklaus. Matching GPS traces to a map. https://blog.mapbox.com/matching-gps-traces-to-a-map-73730197d0e2, 2015.
  35. Bei Pan, Yu Zheng, David Wilkie, and Cyrus Shahabi. Crowd sensing of traffic anomalies based on human mobility and social media. In 21st International Conference on Advances in Geographic Information Systems, SIGSPATIAL'13, pages 334-343. ACM, 2013. Google Scholar
  36. Gang Pan, Guande Qi, Wangsheng Zhang, Shijian Li, Zhaohui Wu, and Laurence Tianruo Yang. Trace analysis and mining for smart cities: issues, methods, and applications. IEEE Communications Magazine, 51(6), 2013. Google Scholar
  37. Matthias Peinhardt and Volker Kaibel. On the bottleneck shortest path problem. Technical report, Technical Report ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2006. Google Scholar
  38. OpenStreetMap project. OSM extract Hong Kong. http://download.openstreetmap.fr/extracts/asia/china/, 2020.
  39. Mohammed A. Quddus, Washington Y. Ochieng, and Robert B. Noland. Current map-matching algorithms for transport applications: State-of-the art and future research directions. Transportation Research Part C: Emerging Technologies, 15(5):312-328, 2007. Google Scholar
  40. Urs Ramer. An iterative procedure for the polygonal approximation of plane curves. Computer graphics and image processing, 1(3):244-256, 1972. Google Scholar
  41. K Reumann and APM Witkam. Optimizing curve segmantation in computer graphics. In International Computing Symposium 1973, pages 467-472, 1974. Google Scholar
  42. Stefan Schrödl, Kiri Wagstaff, Seth Rogers, Pat Langley, and Christopher Wilson. Mining GPS traces for map refinement. Data Mining and Knowledge Discovery, 9(1):59-87, 2004. Google Scholar
  43. Dominik Schultes and Peter Sanders. Dynamic highway-node routing. In 6th International Workshop on Experimental Algorithms, WEA'07, volume 4525 of Lecture Notes in Computer Science, pages 66-79. Springer, 2007. Google Scholar
  44. Junichi Shigezumi, Tatsuya Asai, Hiroaki Morikawa, and Hiroya Inakoshi. A fast algorithm for matching planar maps with minimum Fréchet distances. In 4th International ACM Workshop on Analytics for Big Geospatial Data, BigSpatial@SIGSPATIAL'15, pages 25-34, 2015. Google Scholar
  45. Youze Tang, Andy Diwen Zhu, and Xiaokui Xiao. An efficient algorithm for mapping vehicle trajectories onto road networks. In International Conference on Advances in Geographic Information Systems, SIGSPATIAL'12, pages 601-604. ACM, 2012. Google Scholar
  46. Rolf van Leusden. A novel algorithm for computing the Fréchet distance. Master’s thesis, TU Eindhoven, 2013. Google Scholar
  47. Yilun Wang, Yu Zheng, and Yexiang Xue. Travel time estimation of a path using sparse trajectories. In 20th ACM International Conference on Knowledge Discovery and Data Mining, KDD'14, pages 25-34. ACM, 2014. Google Scholar
  48. Hong Wei, Yin Wang, George Forman, and Yanmin Zhu. Map matching by Fréchet distance and global weight optimization. Technical Paper, page 19, 2013. Google Scholar
  49. Hong Wei, Yin Wang, George Forman, and Yanmin Zhu. Map matching: comparison of approaches using sparse and noisy data. In 21st International Conference on Advances in Geographic Information Systems, SIGSPATIAL'13, pages 434-437. ACM, 2013. Google Scholar
  50. Carola Wenk, Randall Salas, and Dieter Pfoser. Addressing the need for map-matching speed: Localizing global curve-matching algorithms. In 18th International Conference on Scientific and Statistical Database Management, SSDBM'06, pages 379-388, 2006. Google Scholar
  51. Can Yang and Gyozo Gidofalvi. Fast map matching, an algorithm integrating hidden Markov model with precomputation. International Journal of Geographical Information Science, 32(3):547-570, 2018. Google Scholar
  52. Yu Zheng. Trajectory data mining: An overview. ACM Transactions on Intelligent Systems and Technology, 6(3):29:1-29:41, 2015. Google Scholar
  53. Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. Mining interesting locations and travel sequences from GPS trajectories. In 18th International Conference on World Wide Web, WWW'09, pages 791-800. ACM, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact