More Web Proxy on the site http://driver.im/

research-article

Fast Viterbi map matching with tunable weight functions

Authors:

Haibing GuanAuthors Info & Claims

SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems

Pages 613 - 616

https://doi.org/10.1145/2424321.2424430

Published: 06 November 2012 Publication History

Abstract

This paper describes a map matching program submitted to the ACM SIGSPATIAL Cup 2012. We first summarize existing map matching algorithms into three categories, and compare their performance thoroughly. In general, global max-weight methods using the Viterbi dynamic programming algorithm are the most accurate but the accuracy varies at different sampling intervals using different weight functions. Our submission selects a hybrid that improves upon the best two weight functions such that its accuracy is better than both and the performance is robust against varying sampling rates. In addition, we employ many optimization techniques to reduce the overall latency, as the scoring heavily emphasizes on speed. Using the training dataset with manually corrected ground truth, our Java-based program matched all 14,436 samples in 5 seconds on a dual-core 3.3 GHz iCore 3 processor, and achieved 98.9% accuracy.

References

[1]

ACM SIGSPATIAL Cup 2012. http://depts.washington.edu/giscup/home.

[2]

H. Alt, A. Efrat, G. Rote, and C. Wenk. Matching planar maps. Journal of Algorithms, 49(2):262--283, 2003.

Digital Library

[3]

C. A. Blazquez and A. P. Vonderohe. Simple map-matching algorithm applied to intelligent winter maintenance vehicle data. Transportation Research Record, 1935(1):68--76, 2006.

[4]

S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On map-matching vehicle tracking data. In VLDB, 2005.

Digital Library

[5]

J. S. Greenfeld. Matching GPS observations to locations on a digital map. In Transportation Research Board, 2002.

[6]

T. Griffin, Y. Huang, and S. Seals. Routing-based map matching for extracting routes from GPS trajectories. In International Conference on Computing for Geospatial Research & Applications, 2011.

Digital Library

[7]

X. Li, M. Li, W. Shu, and M. Wu. A practical map-matching algorithm for GPS-based vehicular networks in Shanghai urban area. In IET Conference on Wireless, Mobile and Sensor Networks, 2007.

[8]

Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. Map-matching for low-sampling-rate GPS trajectories. In ACM SIGSPATIAL GIS, 2009.

Digital Library

[9]

F. Marchal, J. Hackney, and K. Axhausen. Efficient map matching of large global positioning system data sets: Tests on speed-monitoring experiment in Zürich. Transportation Research Record, 1935(1):93--100, 2005.

[10]

O. Mazhelis. Using recursive Bayesian estimation for matching GPS measurements to imperfect road network data. In Intelligent Transportation Systems, 2010.

[11]

P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. In ACM SIGSPATIAL GIS, 2009.

Digital Library

[12]

O. Pink and B. Hummel. A statistical approach to map matching using road network geometry, topology and vehicular motion constraints. In Intelligent Transportation Systems, 2008.

[13]

M. A. Quddus, W. Ochieng, L. Zhao, and R. Noland. A general map matching algorithm for transport telematics applications. GPS Solutions, 7(3):157--167, 2003.

[14]

A. Thiagarajan, L. Ravindranath, K. LaCurts, S. Madden, H. Balakrishnan, S. Toledo, and J. Eriksson. Vtrack: accurate, energy-aware road traffic delay estimation using mobile phones. In SenSys, 2009.

Digital Library

[15]

N. R. Velaga, M. A. Quddus, and A. L. Bristow. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems. Transportation Research Part C: Emerging Technologies, 17(6):672--683, 2009.

[16]

C. E. White, D. Bernstein, and A. L. Kornhauser. Some map matching algorithms for personal navigation assistants. Transportation Research Part C: Emerging Technologies, 8(1-6):91--108, 2000.

[17]

J. Yang, S. Kang, and K. Chon. The map matching algorithm of GPS data with relatively long polling time intervals. Journal of the Eastern Asia Society for Transportation Studies, 6:2561--2573, 2005.

[18]

Y. Zheng and M. A. Quddus. Weight-based shortest path aided map-matching algorithm for low frequency GPS data. In Transportation Research Board, 2011.

Cited By

Qi HHuang ZChen YZhang YGao Y(2024)Streamlining trajectory map-matching: a framework leveraging spark and GPU-based stream processingInternational Journal of Geographical Information Science10.1080/13658816.2024.233722538:6(1158-1178)Online publication date: 9-Apr-2024
https://doi.org/10.1080/13658816.2024.2337225
Wöltche A(2023)Open source map matching with Markov decision processes: A new method and a detailed benchmark with existing approachesTransactions in GIS10.1111/tgis.1310727:7(1959-1991)Online publication date: 18-Oct-2023
https://doi.org/10.1111/tgis.13107
Wang YXiong RTang PLiu Y(2023)Fast and Reliable Map Matching from Large-Scale Noisy Positioning RecordsJournal of Computing in Civil Engineering10.1061/(ASCE)CP.1943-5487.000105437:1Online publication date: Jan-2023
https://doi.org/10.1061/(ASCE)CP.1943-5487.0001054
Show More Cited By

Index Terms

Fast Viterbi map matching with tunable weight functions
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Data mining
    2. Spatial-temporal systems

Recommendations

Map matching: comparison of approaches using sparse and noisy data
SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

The process of map matching takes a sequence of possibly noisy GPS coordinates from a vehicle trace and estimates the actual road positions---a crucial first step needed by many GPS applications. There has been a plethora of methods for map matching ...
One New Map Matching Model for Vehicle-Borne Navigation System
ICOIP '10: Proceedings of the 2010 International Conference on Optoelectronics and Image Processing - Volume 02

The technique of vehicle-borne navigation system develops rapidly. Map matching is one of the key techniques of the vehicle-borne navigation. General map matching method is based on simple point projection. It often appears matching errors in the face ...
Quick map matching using multi-core CPUs
SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems

The ACM SIGSPATIAL Cup 2012 is about map matching, a problem of correctly matching a sequence of GPS sampling points to the roads on a digital map. This paper describes one of the winning submissions of the competition. The approach applies multi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems

November 2012

642 pages

ISBN:9781450316910

DOI:10.1145/2424321

General Chairs:
Isabel Cruz
University of Illinois at Chicago
,
Craig Knoblock
University of Southern California
,
Program Chairs:
Peer Kröger
Ludwig-Maximilians-Universität München, Germany
,
Egemen Tanin
University of Melbourne, Australia
,
Peter Widmayer
ETH Zürich, Switzerland

Copyright © 2012 ACM.

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]

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGSPATIAL'12

Sponsor:

SIGSPATIAL

SIGSPATIAL'12: SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems

November 6 - 9, 2012

Redondo Beach, California

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
463
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Qi HHuang ZChen YZhang YGao Y(2024)Streamlining trajectory map-matching: a framework leveraging spark and GPU-based stream processingInternational Journal of Geographical Information Science10.1080/13658816.2024.233722538:6(1158-1178)Online publication date: 9-Apr-2024
https://doi.org/10.1080/13658816.2024.2337225
Wöltche A(2023)Open source map matching with Markov decision processes: A new method and a detailed benchmark with existing approachesTransactions in GIS10.1111/tgis.1310727:7(1959-1991)Online publication date: 18-Oct-2023
https://doi.org/10.1111/tgis.13107
Wang YXiong RTang PLiu Y(2023)Fast and Reliable Map Matching from Large-Scale Noisy Positioning RecordsJournal of Computing in Civil Engineering10.1061/(ASCE)CP.1943-5487.000105437:1Online publication date: Jan-2023
https://doi.org/10.1061/(ASCE)CP.1943-5487.0001054
Li WWang YLi DXu X(2022)MCM: A Robust Map Matching Method by Tracking Multiple Road CandidatesAlgorithmic Aspects in Information and Management10.1007/978-3-031-16081-3_20(231-243)Online publication date: 18-Sep-2022
https://doi.org/10.1007/978-3-031-16081-3_20
Zhang HLuo YYu QZheng XLi X(2021)Map-matching approach based on link factor and hidden Markov modelJournal of Intelligent & Fuzzy Systems10.3233/JIFS-202292(1-17)Online publication date: 25-Jan-2021
https://doi.org/10.3233/JIFS-202292
Agafonov AMyasnikov V(2021)Reconstruction of User Trips on Public Transport Using Indirect Information2021 International Conference on Information Technology and Nanotechnology (ITNT)10.1109/ITNT52450.2021.9649301(1-6)Online publication date: 20-Sep-2021
https://doi.org/10.1109/ITNT52450.2021.9649301
Kajioka SSaito TYamamoto DTakahashi N(2021)A Web-Based Geospatial Adjacency Graph Construction Tool for Indoor/Outdoor Beacons2021 IEEE 10th Global Conference on Consumer Electronics (GCCE)10.1109/GCCE53005.2021.9622012(1-2)Online publication date: 12-Oct-2021
https://doi.org/10.1109/GCCE53005.2021.9622012
Karamete BAdhami LGlaser E(2021)An adaptive Markov chain algorithm applied over map-matching of vehicle trip GPS dataGeo-spatial Information Science10.1080/10095020.2020.1866956(1-14)Online publication date: 2-Feb-2021
https://doi.org/10.1080/10095020.2020.1866956
Abbar SMokbel M(2021)The role of AI in digital contact tracingLeveraging Artificial Intelligence in Global Epidemics10.1016/B978-0-323-89777-8.00003-8(203-221)Online publication date: 2021
https://doi.org/10.1016/B978-0-323-89777-8.00003-8
Chen CZhang DWang YHuang HChen CZhang DWang YHuang H(2021)Trajectory Data Map-matchingEnabling Smart Urban Services with GPS Trajectory Data10.1007/978-981-16-0178-1_1(3-24)Online publication date: 2-Apr-2021
https://doi.org/10.1007/978-981-16-0178-1_1
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents