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

被引：15
作者：
Adoni W.Y.H. [1 ]
Nahhal T. [1 ]
Aghezzaf B. [1 ]
Elbyed A. [1 ]
机构：
[1] Laboratoire Informatique Modélisation des Systèmes et Aide à la Décision, Faculty of sciences, Hassan II University of Casablanca, Km 8 Route d’El Jadida, Maarif, B.P 5366, Casablanca
来源：
Journal of Big Data | 2018年 / 5卷 / 01期
关键词：
A[!sup]*[!/sup] algorithm; Big Data; Hadoop; HDFS; Large-scale network; MapReduce; Parallel and distributed computing; Path-finding;
D O I：
10.1186/s40537-018-0125-8
中图分类号：
学科分类号：
摘要：
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. © 2018, The Author(s).
引用
收藏
相关论文
共 38 条
[1]  
OpenStreetMap. OpenStreetMap statistics
[2]  
Hart P.E., Nilsson N.J., Raphael B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans Syst Sci Cybern, 4, 2, pp. 100-107, (1968)
[3]  
Adoni W.Y.H., Nahhal T., Aghezzaf B., Elbyed A., The mapreduce-based approach to improve vehicle controls on big traffic events, International colloquium on logistics and supply chain management (LOGISTIQUA). Rabat: IEEE
[4]  
, 20, pp. 17. p. 1-6, (2017)
[5]  
Djidjev H., Chapuis G., Andonov R., Thulasidasan S., Lavenier D., All-pairs shortest path algorithms for planar graph for gpu-accelerated clusters, J Parallel Distrib Comput, 85, C, pp. 91-103, (2015)
[6]  
Aridhi S., d'Orazio L., Maddouri M., Mephu N.E., Density-based data partitioning strategy to approximate large-scale subgraph mining, Inf Syst, 48, pp. 213-223, (2015)
[7]  
Aridhi S., Lacomme P., Benjamin V., A mapreduce-based approach for shortest path problem in large-scale networks, Eng Appl Artif Intell, 41, C, pp. 151-165, (2015)
[8]  
Aridhi S., Benjamin V., Lacomme P., Ren L., Shortest path resolution using hadoop, MOSIM 2014, 10ème Confèrence Francophone de Modèlisation, Optimisation et Simulation
[9]  
Zhang D., Xiong L., The research of dynamic shortest path based on cloud computing, 12th international conference on computational intelligence and security (CIS). Wuxi: IEEE
[10]  
2016. p, pp. 452-455, (2016)
1234