The MapReduce based approach to improve the all-pair shortest path computation
Abstract
When building sequential algorithms for problems on the graphic network, the algorithms themselves are not only very complex but the complexity of the algorithms also is very big. Thus, sequential algorithms must be parralled to share work and reduce computation time. For above reasons, it is crucial to build parallelization of algorithms in extended graph to find the shortest path. Therefore, a study of algorithm finding the shortest path from a source node to all nodes in the MapReduce architectures is essential to deal with many real problems with huge input data in our daily life. MapReduce architectures processes on (Key, Value) pairs are independent between processes, so multiple processes can be assigned to execute simultaneously on the Hodoop system to reduce calculation time
References
2. Robert Sedgewick, Algorithms in C part 5: graph algorithms (third edition), Addison-Wesley, 2000.
3. V. Dragomir, All-pair shortest path modified matrix multiplication based algorithm for a one-chip MapReduce architecture, U.P.B. Sci. Bull., Series C, 78, 4, pp. 95-108, 2016.
4. Voichiţa DRAGOMIR, Gheorghe M. ŞTEFAN, All-pair shortest path on a hybrid Map-Reduce based architecture, Proceedings of The Romanian Academy, Series A, the publishing House of the Romanian Academy, Volume 20, Number 4/2019, pp. 411–417.
5. Sabeur Aridhi, Vincent Benjamin, Philippe Lacomme, Libo Ren, Shortest path resolutionusing hadoop, MOSIM’14, Nancy – France, 7/11/2014.
6. Wilfried Yves Hamilton Adoni, Tarik Nahhal, Brahim Aghezzaf* and Abdeltif Elbyed, The MapReduce based approach to improve the shortest path computation in large scale road networks: the case of A* algorithm, journal of Big Data, Springer, open access, 2018
7. Wilfried Yves Hamilton Adoni, Tarik Nahhal, Brahim Aghezzaf, and Abdeltif Elbyed, MRA*: Parallel and Distributed Path in Large-Scale Graph Using MapReduce-A* Based Approach, Springer International Publishing AG 2017, pp. 390–401, 2017
8. Sabeur Aridhi, Philippe Lacomme, Libo Ren, Benjamin Vincent, A MapReduce-based approach for shortest path problem in large-scale networks, Elsevier, Journal of Engineering Applications of Artificial Intelligence 41 (2015) 151–165
9. Hadoop, A. Welcome to Apache Hadoop. http://hadoop.apache.org/. Accessed 10 Mar 2017.
10. Ghemawat S, Gobioff H, Leung ST. The google file system. In: ACM SIGOPS operating systems review, vol. 37. New York: ACM; 2003. p. 29–43.
https://doi.org/10.1145/945445.945450.
11. Dean J, Ghemawat S. Mapreduce: simplified data processing on large clusters. Commun ACM. 2008;51(1):107–13.
12. Vavilapalli VK, Seth S, Saha B, Curino C, O’Malley O, Radia S, Reed B, Baldeschwieler E, Murthy AC, Douglas C, Agarwal S, Konar M, Evans R, Graves T, Lowe J, Shah H. Apache hadoop YARN: yet another resource negotiator. In: Proceedings of the 4th annual symposium on cloud computing. Santa Clara: ACM Press; 2013. p. 1– 16.
13. Nguyen Dinh Lau, Tran Quoc Chien, Le Manh Thanh, Improved Computing Performance for Algorithm Finding the Shortest Path in Extended Graph, proceedings of the 2014 international conference on foundations of computer science (FCS’14), USA, pp 14-20, 2014
Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.