Please use this identifier to cite or link to this item:
|Title:||Heuristic optimizations for high-speed low-latency online map matching with probabilistic sequence models||Authors:||Jagadeesh, George Rosario
|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|
Updated on Apr 18, 2021
Updated on Apr 18, 2021
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.