Document Server@UHasselt >
Research >
Research publications >

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
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.
URI: http://hdl.handle.net/1942/23269
DOI: 10.3390/ijgi5110204
ISI #: 000390104200011
ISSN: 2220-9964
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version3.07 MBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.