Consider improving perf by using the UBODT algorithm.

[oldrev]

Hello:

Recently, I found there is a new algorithm called "upper-bounded origin destination table (UBODT)", it's basically a precomputed shortest path hash table:

https://github.com/cyang-kth/fmm

IMHO, since the Dijkstra router is the bottleneck of map matching algorithm, this so-called "UBODT" should have a great chance to improve the performance.

[smattheis]

That's very interesting. Thanks for sharing that. I think it requires a deeper analysis of the algorithm to see if it's a good fit for this library because it could narrow the range of use cases. The focus of this library is (more or less) on the online map matching use case and the possibility to use it for online (real-time) location-based services. Therefore, I'm focusing on strategies that provide a map data structure that is able to be updated during runtime of a service. This, however, could collide with the algorithm as it requires pre-computation of routes. Have you had closer look to the algorithm to make a statement to that? (It seems to be a claim that pre-computation is very fast but it's more the question if the algorithm works if only tiles of the map are pre-computed and if independently pre-computed tiles fit together to give a robust solution.)

[oldrev]

I'm studying it too. Hopefully I can make a contribution in later days.

FYI, the paper can be downloaded from author's home page: https://people.kth.se/~Ecyang/

[oldrev]

Finally, I have implemented the UBODT algorithm in my .NET port (https://github.com/oldrev/mapmatchingkit) of Barefoot successfully. But sadly it not that fast as the paper described :)

The UBODT does a Dijkstra traversal in a bounding length (like limited in 3km) for each vertex in the graph, it's nothing to do with any specific route.

The traversal tree recorded in a table with rows like below: Row(sourceEdge, targetEdge, distance)

And each row mapped in a dictionary with Key(tuple(sourceEdge.sourceVertex, targetEdge.targetVertex)).

With all these information, to find the shortest path between two edges (Es, Et) in hash table T, we can do:

```T[T[Es.targetVertex, Et.sourceVertex].sourceTarget.targetVertex, ... Et.sourceVertex]```

Obviously, if the distance of the path between Es and Et greater than 3km, the algorithm will be failed, on that situation we could fall back to normal Dijkstra algorithm.

[smattheis]

Wow, that's really cool! First, your project and, second, your implementation of UBODT. May I ask a few questions:

• What's the maximum speedup you gained?
• Am I right, if I assume that speedup depends on the sampling rate (which of course correlates with the distance between candidates)? If so, how is the speedup with very low sampling intervals of 1 - 10 seconds?
• Does UBODT precalculate (really) all possible pairs of routes for such a bounding box or is there some kind of selection/filter? How large is the hash table for a specific street map? (Do you keep it in memory or on disk?)

[oldrev]

Q: What's the maximum speedup you gained?

Benchmark shows that in the simple shortest path searching the UBODT is ~16x faster than the naive Dijkstra algorithm. But when I try the real world data to do map-matching, it's slightly slower than your multi-source Dijkstra algorithm.

I'm investigating the reason, it's most likely caused by my flawed implementation :)

Q: Am I right, if I assume that speedup depends on the sampling rate (which of course correlates with the distance between candidates)? If so, how is the speedup with very low sampling intervals of 1 - 10 seconds?

I need more time to do the benchmark things. I'll keep you posted.

Q: Does UBODT precalculate (really) all possible pairs of routes for such a bounding box? How large is the hash table for a specific street map? (Do you keep it in memory or on disk?)

No, there are no "pairs", the UBODT algorithm has two stages: the UBODT table generation and the shortest path searching. The generation stage is a single-source Dijkstra traversal without a specific target but the distance limition (3km) from source vertex to last visited vertex.

For my testing graph, it has 5278 edges, the number of rows in the UBODT is 298,258. Right now I'm storing them in a simple in-memory hash table, but since it's a "precomputation" data structure just like the spatial index, the table can be stored in a database or something else.