Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/2424321.2424430acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
research-article

Fast Viterbi map matching with tunable weight functions

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.
[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.
[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.
[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.
[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.
[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.
[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

View all
  • (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
  • (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
  • (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
  • Show More Cited By

Recommendations

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
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

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2012

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Fréchet distance
  2. GPS
  3. Viterbi
  4. map matching

Qualifiers

  • Research-article

Conference

SIGSPATIAL'12
Sponsor:

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)10
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (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
  • (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
  • (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
  • (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
  • (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
  • (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
  • (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
  • (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
  • (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
  • (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
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media