Minimum Cost Path for a Shared Nothing Architecture

Maytham Safar

Computer Engineering Department, Kuwait University, Kuwait

Abstract: 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, precomputation 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 subproblems by exploiting a set of intermediate nodes that the shortest path passes through. We also investigate the impact of replicating subgraphs 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 sizeup, and scaleup results than the parallel algorithm.

Keywords: Shortest path, GIS system, intelligent transportation systems, shared nothing architecture, teradata multimedia database.

Received May 24, 2004; accepted July 31, 2004