Plugin boosting : OpenCL compatibility

[CorentinLemaitre]

Hello,

I have try your plugin and achieve to make it work for a small example and small network. Well done ! I understand that it is huge calculation to do but it take lot of time to do.
I wonder what could speedup the process ? Is there any data format that work better ? is there a compatibility with GPU acceleration (openCL treatment) ? Or multi threading ?

[jagodki]

Hi,

thank you very much for your message. Glad to hear, that the plugin works for you :)

The computation time is a big problem in the field of map matching. I cannot really test the computation time, because currently I am working on a MBP from 2010. Every computation is slow on this machine ^^

There are several papers concerning the improvement of computation time of map matching algorithms. One approach is to use multithreading, that is right. But I think, this will not be the big game changer. If you look into the QGIS log after running the plugin, you can find messages of the plugin. A message will be written to the log after each main computation step. The big problem is the calculation of all the transitions between the candidates. The count of transitions should (more or less) grow in an exponential way, when the number of all candidates is increasing. All the other steps (e.g. calculate candidates, Viterbi algorithm) are even fast on my machine 😄

Another approach could be to implement a second algorithm, that is faster then mine. Anita Graser and her colleagues from the AIT wrote a paper about this topic. I will implement this algorithm in a future version. But at the moment I am working on another project, so I do not know, when I have time to realize it. Definitely not in 2018, but somewhere in 2019 should it be possible.

The input data has an impact on the computation time. A preprocessing of your data could be helpful. For example: you could reduce your network if you calculate buffers of your trajectory and remove all linestrings of the network, which are not interacting with the buffers. But I think, the will not save so many computation time, because the count of the transitions will be more or less the same.

Last but not least: there could also be a bad implementation of the mathematical model in the source code (I hope not, but it is possible). I wanted to create a plugin, that does not need any installed python modules. This should make the installation of the plugin easier. Using OpenCL would not be applicable for this philosophy. But this could be changed in a future release, if there would be a big improvement. Problem is, that I do not have any experience with OpenCL. But if you have it, you are welcome to work with me on the plugin 😺. The next days I will look for a a good tutorial/book/paper etc. of OpenCL in Python to get a feeling for how many changes on the code will be necessary. I will write you the results of my investigations.

Sincerely,
Christoph

[jagodki]

I am sorry for my late response, but here it is 😃:

I thought about different things to improve the computation time. There are three possibilities, which I can imagine at the moment:

• implementation of multithreading
• add another (faster) algorithm
• enable GPU-acceleration

I created a new project for this topic. The first two points have more relevance for me than the third. But as I mentioned above: at the moment I am working on a another project. When I finished that project, I will return to this plugin. I will inform you later about new versions and the result of the improvements.

[jagodki]

I found out, that I do the routing between two candidates/point geometries twice. If I would reuse the routing result, the performance should be better. I think, I can create an enhanced version in 1 week and start the work on it immediately. The problem is written down in issue #12 and marked in the GitHub-project.

[jagodki]

@CorentinLemaitre I uploaded a new version of the plugin (2.1.0). This version reuses calculation results from routing (Dijkstra), i.e. routing will be called less times during processing. I noticed an improvement in computation time between 40% and 50% with my test data. Please let me know, if it works for you or when the speed improvements are not good enough.

[CorentinLemaitre]

@jagodki super Cool !
I will test that ASAP, i hope to get enough time before Xmas. I will give you feedback.

[jagodki]

@CorentinLemaitre did you already tested it?

[CorentinLemaitre]

Nope i don't... sorry i will get no time until may.