Boosting Performance of Map Matching Algorithms by Parallelization on Graphics Processors

In this paper existing map matching algorithms are combined and modified such, that the resulting algorithm is suitable for the implementation on the graphics processing unit (GPU). The map matching algorithm implemented on GPU consists of a geometrical and topological processing step, which provides high accuracy with high efficiency at the same time. An important building block of the implementation is the parallelization of the R*-tree search. An efficient implementation is achieved by high data parallelism and minimal divergence between execution blocks. The presented map matching algorithm performs better than available open source implementations.