research-article

An algorithm for map matching given incomplete road data

Authors:

Jan-Henrik Haunert,

Benedikt BudigAuthors Info & Claims

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

Pages 510 - 513

https://doi.org/10.1145/2424321.2424402

Published: 06 November 2012 Publication History

Get Access

Abstract

We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336--343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians.

References

[1]

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

Digital Library

Google Scholar

[2]

J. Eisner, S. Funke, A. Herbst, A. Spillner, and S. Storandt. Algorithms for matching and predicting trajectories. In Proc. Workshop Algorithm Engineering and Experiments (ALENEX '11), pages 84--95. SIAM, 2011.

Crossref

Google Scholar

[3]

Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. Map-matching for low-sampling-rate GPS trajectories. In Proc. 17th ACM SIGSPATIAL Internat. Conf. Advances in Geographic Information Systems (GIS '09), pages 352--361. ACM, 2009.

Digital Library

Google Scholar

[4]

J. S. B. Mitchell and C. H. Papadimitriou. The weighted region problem: finding shortest paths through a weighted planar subdivision. J. ACM, 38(1):18--73, 1991.

Digital Library

Google Scholar

[5]

P. Newson and J. Krumm. Hidden markov map matching through noise and sparseness. In Proc. 17th ACM SIGSPATIAL Internat. Conf. Advances in Geographic Information Systems (GIS '09), pages 336--343. ACM, 2009.

Digital Library

Google Scholar

[6]

F. C. Pereira, H. Costa, and N. M. Pereira. An off-line map-matching algorithm for incomplete map databases. European Transport Research Review, 1(3):107--124, 2009.

Crossref

Google Scholar

[7]

M. A. Quddus, W. Y. Ochieng, and R. 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.

Crossref

Google Scholar

[8]

L. R. Rabiner and B. H. Juang. An introduction to hidden Markov models. IEEE ASSP Magazine, pages 4--15, January 1986.

Crossref

Google Scholar

Cited By

View all

Fosgerau MŁukawska MPaulsen MRasmussen T(2023)Bikeability and the induced demand for cyclingProceedings of the National Academy of Sciences10.1073/pnas.2220515120120:16Online publication date: 11-Apr-2023
https://doi.org/10.1073/pnas.2220515120
de Lange Nde Lange N(2023)Basic Concepts of Computer ScienceGeoinformatics in Theory and Practice10.1007/978-3-662-65758-4_3(55-130)Online publication date: 24-Jun-2023
https://doi.org/10.1007/978-3-662-65758-4_3
Forsch AFunke SHaunert JStorandt S(2023)Efficient Mining of Volunteered Trajectory DatasetsVolunteered Geographic Information10.1007/978-3-031-35374-1_3(43-77)Online publication date: 9-Dec-2023
https://doi.org/10.1007/978-3-031-35374-1_3
Show More Cited By

Index Terms

An algorithm for map matching given incomplete road data

Recommendations

Hidden Markov map matching based on trajectory segmentation with heading homogeneity
Abstract
Map matching is to locate GPS trajectories onto the road networks, which is an important preprocessing step for many applications based on GPS trajectories. Currently, hidden Markov model is one of the most widely used methods for map matching. ...
Map-matching algorithm for large-scale low-frequency floating car data

Large-scale global positioning system GPS positioning information of floating cars has been recognised as a major data source for many transportation applications. Mapping large-scale low-frequency floating car data FCD onto the road network is very ...
A New Road Network Model and Its Application in a Traffic Information System
ICAS '08: Proceedings of the Fourth International Conference on Autonomic and Autonomous Systems

The traditional road network used in the traffic information system consider little about the complicated structure of the road, and regard all roads as the same. However, in the Traffic Information System using the Floating Car Data (FCD), the GPS ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

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

17
Total Citations
View Citations
339
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fosgerau MŁukawska MPaulsen MRasmussen T(2023)Bikeability and the induced demand for cyclingProceedings of the National Academy of Sciences10.1073/pnas.2220515120120:16Online publication date: 11-Apr-2023
https://doi.org/10.1073/pnas.2220515120
de Lange Nde Lange N(2023)Basic Concepts of Computer ScienceGeoinformatics in Theory and Practice10.1007/978-3-662-65758-4_3(55-130)Online publication date: 24-Jun-2023
https://doi.org/10.1007/978-3-662-65758-4_3
Forsch AFunke SHaunert JStorandt S(2023)Efficient Mining of Volunteered Trajectory DatasetsVolunteered Geographic Information10.1007/978-3-031-35374-1_3(43-77)Online publication date: 9-Dec-2023
https://doi.org/10.1007/978-3-031-35374-1_3
Köppl D(2022)Linking Off-Road Points to Routing NetworksAlgorithms10.3390/a1505016315:5(163)Online publication date: 12-May-2022
https://doi.org/10.3390/a15050163
Jiang LChen CChen CHuang HGuo B(2022)From driving trajectories to driving paths: a survey on map-matching AlgorithmsCCF Transactions on Pervasive Computing and Interaction10.1007/s42486-022-00101-w4:3(252-267)Online publication date: 23-May-2022
https://doi.org/10.1007/s42486-022-00101-w
Custers BMeulemans WSpeckmann BVerbeek K(2021)Route Reconstruction from Traffic Flow via Representative TrajectoriesProceedings of the 29th International Conference on Advances in Geographic Information Systems10.1145/3474717.3483650(41-52)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3474717.3483650
Lucks LKlingbeil LPlümer LDehbi Y(2021)Improving trajectory estimation using 3D city models and kinematic point cloudsTransactions in GIS10.1111/tgis.1271925:1(238-260)Online publication date: 2-Jan-2021
https://doi.org/10.1111/tgis.12719
de Lange Nde Lange N(2020)Grundlagen aus der InformatikGeoinformatik in Theorie und Praxis10.1007/978-3-662-60709-1_3(53-126)Online publication date: 3-Mar-2020
https://doi.org/10.1007/978-3-662-60709-1_3
Murphy JPao YYuen A(2019)Map matching when the map is wrongProceedings of the 12th ACM SIGSPATIAL International Workshop on Computational Transportation Science10.1145/3357000.3366143(1-10)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1145/3357000.3366143
Sasaki YYu JIshikawa Y(2019)Road Segment Interpolation for Incomplete Road Data2019 IEEE International Conference on Big Data and Smart Computing (BigComp)10.1109/BIGCOMP.2019.8679461(1-8)Online publication date: Feb-2019
https://doi.org/10.1109/BIGCOMP.2019.8679461
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.

Cited By

Index Terms

Recommendations

Hidden Markov map matching based on trajectory segmentation with heading homogeneity

Map-matching algorithm for large-scale low-frequency floating car data

A New Road Network Model and Its Application in a Traffic Information System