[Routing] Fast Routing Engine - State of Play

[Dennis Luxen]

> did someone think of / try a MapReduce approach for preprocessing
> contraction hierarchies? maybe it could help parallelize computation
> and iteratively approximate betweeness centrality to pick the "right"
> nodes for higher "levels"..

The central element of the preprocessing is node contraction. Node
ordering is computed on the fly. The contraction of nodes can be
parallelized by identifying independent node sets and proceeding
iteratively until all are contracted. See Vetters work [1] for an
explanation of that way of preprocessing. There is also a distributed
variant [2].

The problem with map/reduce is that a (somehow) parallel node
contraction step does alter a shared memory data structure. And this
does not work for the m/r setting.

> btw what is it anyway that guarantees the algorithm to find a/the
> shortest path in the end? if only higher level (shortcut) edges are
> expanded and lower ones are pruned, why aren't there any shorter
> paths that stay undiscovered? (plz excuse if this the wrong place to
> ask.. but this keeps puzzling me)

In short: Shortcute preserve shortest path distances and are only
omitted of the shortcut does not represent a shortest path.

Maybe we should take any further technical discussions off the list.

--Dennis

[1] http://algo2.iti.kit.edu/1366.php
[2] http://algo2.iti.kit.edu/1590.php