The MapReduce-based approach to improve the shortest path computation in large-scale road networks: the case of A* algorithm

Journal of Big Data

Abdeltif Elbyed¹  Tarik Nahhal¹  Brahim Aghezzaf¹  Wilfried Yves Hamilton Adoni¹ 

[1] Laboratoire Informatique Modélisation des Systèmes et Aide à la Décision, Faculty of sciences, Hassan II University of Casablanca;

关键词: Path-finding;    Large-scale network;    A* algorithm;    Big Data;    Hadoop;    MapReduce;   

DOI  :  10.1186/s40537-018-0125-8

来源: DOAJ

【 摘 要 】

Abstract This paper deals with an efficient parallel and distributed framework for intensive computation with A* algorithm based on MapReduce concept. The A* algorithm is one of the most popular graph traversal algorithm used in route guidance. It requires exponential time computation and very costly hardware to compute the shortest path on large-scale networks. Thus, it is necessary to reduce the time complexity while exploiting a low cost commodity hardwares. To cope with this situation, we propose a novel approach that reduces the A* algorithm into a set of Map and Reduce tasks for running the path computation on Hadoop MapReduce framework. An application on real road networks illustrates the feasibility and reliability of the proposed framework. The experiments performed on a 6-node Hadoop cluster proves that the proposed approach outperforms A* algorithm and achieves significant gain in terms of computation time.

【 授权许可】

Unknown