short-paper

Routing-based map matching for extracting routes from GPS trajectories

Authors:

Terry Griffin,

Yan Huang,

Shawn SealsAuthors Info & Claims

COM.Geo '11: Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications

Article No.: 24, Pages 1 - 6

https://doi.org/10.1145/1999320.1999344

Published: 23 May 2011 Publication History

Get Access

Abstract

This paper introduces a novel offline map matching approach. We develop a routing-based map matching approach for standardizing identified routes in a collected set of GPS trajectories. Our approach first identifies key waypoints in a user's GPS trajectory using a modified Peucker curve reduction algorithm. Subsequently, it sends the key waypoints to a black-box driving directions service which returns a route utilizing each of the key waypoints. The returned route is a standardized representation of the original GPS trajectory constructed using the minimum necessary set of points. A filter-and-refine approach is used to identify the incorrect portion of the returned route and a refine step is carried out by eliminating the waypoints what leads to the incorrect matching. Experiments results showed that the proposed approach works well for a data-set of 10 volunteers each collecting data an average of 34.3 days.

References

[1]

H. Alt, A. Efrat, G. Rote, and C. Wenk. Matching planar maps. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 589--598. Society for Industrial and Applied Mathematics, 2003.

Digital Library

Google Scholar

[2]

L. Cao and J. Krumm. From gps traces to a routable road map. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS '09, pages 3--12, New York, NY, USA, 2009. ACM.

Digital Library

Google Scholar

[3]

E. Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269--271, 1959.

Digital Library

Google Scholar

[4]

D. Douglas and T. 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.

Crossref

Google Scholar

[5]

S. Erle, R. Gibson, and J. Walsh. Mapping hacks: tips & tools for electronic cartography. O'Reilly Media, Inc., 2005.

Digital Library

Google Scholar

[6]

P. Hart, N. Nilsson, and B. Raphael. Correction to a formal basis for the heuristic determination of minimum cost paths. ACM SIGART Bulletin, (37):28--29, 1972.

Digital Library

Google Scholar

[7]

P. Hu. Summary of Travel Trends 2001 National Household Travel Survey. Technical report, ORNL, 2005.

Google Scholar

[8]

F. Marchal, J. Hackney, and K. Axhausen. Efficient Map-Matching of Large GPS Data Sets-Tests on a Speed Monitoring Experiment in Zurich, volume 244 of Arbeitsbericht Verkehrs und Raumplanung. 2004.

Google Scholar

[9]

J. Quinlan. C4. 5: programs for machine learning. Morgan Kaufmann, 1993.

Digital Library

Google Scholar

[10]

H. Yin and O. Wolfson. A weight-based map matching method in moving objects databases. 2004.

Google Scholar

Cited By

View all

Gupta AShanker U(2022)A Comprehensive Review of Map-Matching TechniquesInternational Journal of Web Services Research10.4018/IJWSR.30624319:1(1-32)Online publication date: 1-Jan-2022
https://doi.org/10.4018/IJWSR.306243
Hao HWang LXia ZYu ZGu JFu N(2021)Traffic Congestion Prediction: A Spatial-Temporal Context Embedding and Metric Learning Approach2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00068(498-505)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00068
Chatterjee SSamanta SMandal R(2021)Automated High Precision Path Annotations on Digital Map from Crowdsourced GPS TracesEmerging Technologies in Data Mining and Information Security10.1007/978-981-15-9774-9_85(931-946)Online publication date: 5-May-2021
https://doi.org/10.1007/978-981-15-9774-9_85
Show More Cited By

Index Terms

Routing-based map matching for extracting routes from GPS trajectories
1. Information systems
  1. World Wide Web
    1. Web applications
    2. Web services

Recommendations

Map-matching for low-sampling-rate GPS trajectories
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Map-matching is the process of aligning a sequence of observed user positions with the road network on a digital map. It is a fundamental pre-processing step for many applications, such as moving object management, traffic flow analysis, and driving ...
Backbone-based location-aided routing algorithm to reduce control packets of AODV protocol
Mobility '06: Proceedings of the 3rd international conference on Mobile technology, applications & systems

A mobile Ad hoc network (MANETs) consists of wireless hosts that may move often. Movements of hosts result in changes in routes, requiring some mechanisms for determining new routes. The well-known Ad hoc On-demand Distance Vector (AODV) protocol ...
Performance Analysis of a Propagation Territory-based Routing in MANETs with Obstacles
MISNC '17: Proceedings of the 4th Multidisciplinary International Social Networks Conference

This study considers constructing an efficient routing protocol in MANETs with obstacles. We take advantage of the location information provided by Global Position System (GPS) and propose a novel greedy propagation territory-based routing mechanism to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COM.Geo '11: Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications

May 2011

292 pages

ISBN:9781450306812

DOI:10.1145/1999320

Conference Chair:
Lindi Liao

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

COM.Geo '11

COM.Geo '11: 2nd International Conference on Computing for Geospatial Research & Application

May 23 - 25, 2011

DC, Washington, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
555
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gupta AShanker U(2022)A Comprehensive Review of Map-Matching TechniquesInternational Journal of Web Services Research10.4018/IJWSR.30624319:1(1-32)Online publication date: 1-Jan-2022
https://doi.org/10.4018/IJWSR.306243
Hao HWang LXia ZYu ZGu JFu N(2021)Traffic Congestion Prediction: A Spatial-Temporal Context Embedding and Metric Learning Approach2021 IEEE 27th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS53394.2021.00068(498-505)Online publication date: Dec-2021
https://doi.org/10.1109/ICPADS53394.2021.00068
Chatterjee SSamanta SMandal R(2021)Automated High Precision Path Annotations on Digital Map from Crowdsourced GPS TracesEmerging Technologies in Data Mining and Information Security10.1007/978-981-15-9774-9_85(931-946)Online publication date: 5-May-2021
https://doi.org/10.1007/978-981-15-9774-9_85
Luo AChen SXv B(2017)Enhanced Map-Matching Algorithm with a Hidden Markov Model for Mobile Phone PositioningISPRS International Journal of Geo-Information10.3390/ijgi61103276:11(327)Online publication date: 30-Oct-2017
https://doi.org/10.3390/ijgi6110327
Mandal RAgarwal NNandi SSaha S(2014)Personalised route-map generation using crowd sourced GPS traces2014 2nd International Conference on Business and Information Management (ICBIM)10.1109/ICBIM.2014.6970965(154-158)Online publication date: Jan-2014
https://doi.org/10.1109/ICBIM.2014.6970965
Wei HWang YForman GZhu YKnoblock CSchneider MKröger PKrumm JWidmayer P(2013)Map matchingProceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2525314.2525456(444-447)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2525314.2525456
Akai YHiromori AUmedu TYamaguchi HHigashino T(2013)Mitigating location and speed errors in floating car data using context-based accuracy estimation2013 13th International Conference on ITS Telecommunications (ITST)10.1109/ITST.2013.6685529(104-110)Online publication date: Nov-2013
https://doi.org/10.1109/ITST.2013.6685529
Wei HWang YForman GZhu YGuan HCruz IKnoblock CKröger PTanin EWidmayer P(2012)Fast Viterbi map matching with tunable weight functionsProceedings of the 20th International Conference on Advances in Geographic Information Systems10.1145/2424321.2424430(613-616)Online publication date: 6-Nov-2012
https://dl.acm.org/doi/10.1145/2424321.2424430
Santos MPereira RLeal A(2012)GBUS - Route GeoTracer2012 First International Workshop on Vehicular Traffic Management for Smart Cities (VTM)10.1109/VTM.2012.6398697(1-6)Online publication date: Nov-2012
https://doi.org/10.1109/VTM.2012.6398697

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Map-matching for low-sampling-rate GPS trajectories

Backbone-based location-aided routing algorithm to reduce control packets of AODV protocol

Performance Analysis of a Propagation Territory-based Routing in MANETs with Obstacles