Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/145765
Title: Heuristic optimizations for high-speed low-latency online map matching with probabilistic sequence models
Authors: Jagadeesh, George Rosario
Srikanthan, Thambipillai
Keywords: Engineering::Computer science and engineering
Issue Date: 2016
Source: Jagadeesh, G. R., & Srikanthan, T. (2016). Heuristic optimizations for high-speed low-latency online map matching with probabilistic sequence models. Proceedings of the 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC), 2565-2570. doi:10.1109/ITSC.2016.7795968
Abstract: The computation speed and output latency of map matching are important considerations when processing location data, especially smartphone-generated noisy and sparse data, from a large number of users for real-time transportation applications. In this paper, we examine the factors affecting the efficiency of online map matching algorithms that are based on probabilistic sequence models such as Hidden Markov Models (HMM) and present several heuristic optimizations to improve their speed and latency. As shortest path computations account for most of the running time of probabilistic map matching algorithms, we propose a method for reducing the total number of such computations by pruning unlikely states in the probabilistic sequence model. Furthermore, we speed up the one-to-many shortest path computations by limiting the search space to an elliptical area that encompasses all the targeted destinations. We present a technique for reducing the latency of the Viterbi algorithm used to find the most likely state sequence in a HMM or a similar model. This technique enables the early output of partial state sequences based on an estimate of the probability of a state being part of the eventual most likely sequence. Experiments using real-world location data show that the heuristic optimizations significantly reduce the running time and output latency with negligible loss of accuracy.
URI: https://hdl.handle.net/10356/145765
ISBN: 978-1-5090-1889-5
DOI: 10.1109/ITSC.2016.7795968
Rights: © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.1109/ITSC.2016.7795968
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Conference Papers

Files in This Item:
File Description SizeFormat 
C16.pdf653.64 kBAdobe PDFView/Open

Page view(s)

25
Updated on Apr 18, 2021

Download(s)

7
Updated on Apr 18, 2021

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.