Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/23269
Title: | Uncertainty-Based Map Matching: The Space-Time Prism and k-Shortest Path Algorithm | Authors: | KUIJPERS, Bart MOELANS, Bart OTHMAN, Walied VAISMAN, Alejandro |
Issue Date: | 2016 | Publisher: | MDPI AG | Source: | ISPRS INTERNATIONAL JOURNAL OF GEO-INFORMATION, 5(11) (Art N° 204) | Abstract: | Location-aware devices can be used to record the positions of moving objects for further spatio-temporal data analysis. For instance, we can analyze the routes followed by a person or a group of people, to discover hidden patterns in trajectory data. Typically, the positions of moving objects are registered by GPS devices, and most of the time, the recorded positions do not match the road actually followed by the object carrying the device, due to different sources of errors. Thus, matching the moving object's actual position to a location on a digital map is required. The problem of matching GPS-recorded positions to a road network is called map matching (MM). Although many algorithms have been proposed to solve this problem, few of them consider the uncertainty caused by the absence of information about the moving object's position in-between consecutive recorded locations. In this paper, we study the relationship between map matching and uncertainty, and we propose a novel MM algorithm that uses space-time prisms in combination with weighted k-shortest path algorithms. We applied our algorithm to real-world cases and to computer-generated trajectory samples with a variety of properties. We compare our results against a number of well-known algorithms that we have also implemented and show that it outperforms existing algorithms, allowing us to obtain better matches, with a negligible loss in performance. In addition, we propose a novel accuracy measure that allows a better comparison between different MM algorithms. We applied this novel measure to compare our algorithm against existing algorithms. | Notes: | [Kuijpers, Bart; Moelans, Bart; Othman, Walied] UHasselt Hasselt Univ & Transnat Univ Limburg, Databases & Theoret Comp Sci Res Grp, Agoralaan, B-3590 Diepenbeek, Belgium. [Moelans, Bart] VikingCo, B-3500 Hasselt, Belgium. [Vaisman, Alejandro] Inst Tecnol Buenos Aires 1106, RA-1106 Buenos Aires, DF, Argentina. | Keywords: | map matching; trajectory and moving object data; space-time prism; k-shortest path algorithm;map matching; trajectory and moving object data; space-time prism; k-shortest path algorithm | Document URI: | http://hdl.handle.net/1942/23269 | e-ISSN: | 2220-9964 | DOI: | 10.3390/ijgi5110204 | ISI #: | 000390104200011 | Rights: | (c) 2016 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC-BY) license (http://creativecommons.org/licenses/by/4.0/). | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2018 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
kuijpers 1.pdf | Published version | 3.07 MB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
9
checked on Apr 22, 2024
Page view(s)
72
checked on Sep 5, 2022
Download(s)
106
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.