Minimum cost path for a shared nothing architecture

Abstract EN

Computing the minimum cost path is a key requirement in Intelligent Transportation Systems (ITS) and in some Geographical Information Systems (GIS) applications.

The major characteristics of these systems are the facts that the underlying transportation graph is large in size and the computation is under time constraint.

Due to the insufficiency of the classic algorithms under these settings, recent studies have focused on speeding the computation by employing alternative techniques such as heuristics, precipitation and parallelization.

In this study, we investigate solutions assuming a shared nothing architecture (i.

e., Teradata multimedia database system) as a way of speeding up the computation further.

We build our algorithms on a recently developed graph model, Hierarchical mulTigraph (HiTi), and describe both concurrent and parallel versions of the algorithms.

The concurrent algorithm allows simultaneous exploration of the search space by utilizing dynamically created agents across multiple disk nodes, which is efficiently supported by the Teradata multimedia database system architecture.

The parallel algorithm breaks the problem into a set of smaller sub problems by exploiting a set of intermediate nodes that the shortest path passes through.

We also investigate the impact of replicating sub graphs in the performance of our algorithms.

We evaluated our algorithms via a simulation study and demonstrated that our concurrent and parallel algorithms show almost a linear speedup as the number of disk / CPU nodes is increased.

Concurrent algorithm exhibits better size up, and scale up results than the parallel algorithm.