International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 12, No. 3, 8 Jun. 2020
Cover page and Table of Contents: PDF (size: 500KB)
MapReduce Algorithm for Single Source Shortest Path Problem
Full Text (PDF, 500KB), PP.11-21
Views: 0 Downloads: 0
Author(s)
Praveen Kumar
1,*
Anil K. Singh
1
Index Terms
BFS, Cloud Computing, DSMR, MapReduce, Shortest Path
Abstract
Computing single source shortest path is a popular problem in graph theory, extensively applied in many areas like computer networks, operation research and complex network analysis. SSSP is difficult to parallelize efficiently as more parallelization leads to more work done by any algorithm. MapReduce is a popular programming framework for large data processing in distributed and cloud environments. In this paper, we have proposed MR-DSMR, a Map reduce version of Dijkstra Strip-mined Relaxation (DSMR) algorithm and MR3-BFS algorithms. We have compared the performance of both the algorithms with BFS. It is observed that MR-DSMR takes lesser communication and computation time compared to existing algorithms.
Cite This Paper
Praveen Kumar, Anil Kumar Singh, "MapReduce Algorithm for Single Source Shortest Path Problem", International Journal of Computer Network and Information Security(IJCNIS), Vol.12, No.3, pp.11-21, 2020. DOI: 10.5815/ijcnis.2020.03.02
Reference
[1] Y.-L. Chou, H. E. Romeijn, R. L. Smith, “Approximating shortest paths in large-scale networks with an application to intelligent transportation systems”, INFORMS J. on Computing 10 (2) (1998) 163-179.
[2] A. Selamat, M. Zolfpour-Arokhlo, S. Z. Hashim and M. H. Selamat, "A fast path planning algorithm for route guidance system," 2011 IEEE International Conference on Systems, Man, and Cybernetics, Anchorage, AK, 2011, pp. 2773-2778.
[3] M. Barth'elemy, “Betweenness centrality in large complex networks”, The European Physical Journal B - Condensed Matter and Complex Systems 38 (2) 163-168.
[4] Wasserman, S., & Faust, K. (1994). “Social Network Analysis: Methods and Applications” (Structural Analysis in the Social Sciences). Cambridge: Cambridge University Press.
[5] ]J. Dean, S. Ghemawat, “Mapreduce: Simplified data processing on large clusters”, Commun. ACM 51 (1) (2008) 107-113.
[6] Amazon-AWSEC2 (2016 (accessed May 31, 2019)). URL http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/concepts.html
[7] A. D. Sarma, F. N. Afrati, S. Salihoglu, J. D. Ullman, “Upper and lower bounds on the cost of a map-reduce computation”, Proc. VLDB Endow 6 (4)(2013) 277-288.
[8] E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik 1 (1) 269-271.
[9] R. Bellman, “On a routing problem”, Quarterly of Applied Mathematics 16(1958) 87-90.
[10] A. Crauser, K. Mehlhorn, U. Meyer, P. Sanders, “A parallelization of dijkstra's shortest path algorithm”, in: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, MFCS '98, 1998, pp. 722-731.
[11] J. Lin, C. Dyer, “Data-intensive text processing with mapreduce”, Synthesis Lectures on Human Language Technologies 3 (1) (2010) 1-177.
[12] Maleki, S., Nguyen, D., Lenharth, A., Garzaran, M. J., Padua, D. A., & Pingali, K. (2016). “DSMR: A parallel algorithm for Single-Source Shortest Path problem”. In Proceedings of the 2016 International Conference on Supercomputing, ICS 2016
[13] Jimmy Lin; Chris Dyer, "Data-Intensive Text Processing with MapReduce," in Data-Intensive Text Processing with MapReduce , , Morgan & Claypool, 2010, pp.
[14] Kajdanowicz, T., Kazienko, P., & Indyk, W. (2014). “Parallel Processing of Large Graphs”. Future Generation Comp. Syst., 32, 324-337.
[15] Jimmy Lin and Michael Schatz. 2010. “Design patterns for efficient graph algorithms in MapReduce. In Proceedings of the Eighth Workshop on Mining and Learning with Graphs (MLG '10). ACM, New York, NY, USA, 78-85
[16] Muhammad Amber Hassaan, Martin Burtscher, and Keshav Pingali. 2011. “Ordered vs. unordered: a comparison of parallelism and work-efficiency in irregular algorithms”. In Proceedings of the 16th ACM symposium on Principles and practice of parallel programming (PPoPP '11). ACM, New York, NY, USA, 3-12.
[17] Keshav Pingali, Donald Nguyen, Milind Kulkarni, Martin Burtscher, M. Amber Hassaan, Rashid Kaleem, Tsung-Hsien Lee, Andrew Lenharth, Roman Manevich, Mario Méndez-Lojo, Dimitrios Prountzos, and Xin Sui. 2011. “The tao of parallelism in algorithms”. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '11). ACM, New York, NY, USA, 12-25.
[18] Ulrich Meyer and Peter Sanders. 1998. “Delta-Stepping: A Parallel Single Source Shortest Path Algorithm”. In Proceedings of the 6th Annual European Symposium on Algorithms (ESA '98), Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, and Geppino Pucci (Eds.). Springer-Verlag, London, UK, UK, 393-404.
[19] V. T. Chakaravarthy, F. Checconi, P. Murali, F. Petrini and Y. Sabharwal, "Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems," in IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 7, pp. 2031-2045, 1 July 2017.
[20] Zalewski, M., Kanewala, T. A., Firoz, J. S., & Lumsdaine, A. (2014, November). “Distributed control: priority scheduling for single source shortest paths without synchronization”. In Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms (pp. 17-24). IEEE Press.
[21] Firoz, J. S., Barnas, M., Zalewski, M., & Lumsdaine, A. (2015, December). “Comparison Of Single Source Shortest Path Algorithms On Two Recent Asynchronous Many-task Runtime Systems”. In Parallel and Distributed Systems (ICPADS), 2015 IEEE 21st International Conference on (pp. 674-681).
[22] ]Harshvardhan, A. Fidel, N. M. Amato, and L. Rauch-werger, "KLA: A New Algorithmic Paradigm for Parallel Graph Computations, "in Proceedngs of the 23rd International conference on Parallel Architectures and Compilation. ACM, 2014, pp27-38
[23] Guy E. Blelloch, Yan Gu, Yihan Sun, and Kanat Tangwongsan. 2016. “Parallel Shortest Paths Using Radius Stepping”. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '16). ACM, New York, NY, USA, 443-454.
[24] A. Crauser, K. Mehlhorn, U. Meyer, P. Sanders, “A parallelization of dijkstra's shortest path algorithm”, in: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, MFCS '98, 1998, pp. 722-731.
[25] G. S. Brodal, J. L. Träff, C. D. Zaroliagis, “A parallel priority queue with constant time operations”, Journal of Parallel and Distributed Computing 49 (1) (1998) 4-21.
[26] G. S. Brodal, J. L. Träff, C. D. Zaroliagis, “A parallel priority data structure with applications,” in: Parallel Processing Symposium, 1997. Proceedings., 11th International, 1997, pp. 689-693.
[27] J. R. Crobak, J. W. Berry, K. Madduri, D. A. Bader, “Advanced shortest paths algorithms on a massively-multithreaded architecture”, in: Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, 2007, pp. 1-8.
[28] M. Thorup, “Undirected single source shortest paths in linear time”, in: Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, 1997, pp. 12-21.
[29] M. Papaefthymiou, J. Rodrigue, “Implementing parallel shortest-paths algorithms”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 30 (1997) 59-68.
[30] Zalewski, M., Kanewala, T. A., Firoz, J. S., & Lumsdaine, A. (2014, November). “Distributed control: priority scheduling for single source shortest paths without synchronization”. In Proceedings of the 4th Workshop on Irregular Applications: Architectures and Algorithms (pp. 17-24). IEEE Press.
[31] S. N. Srirama, P. Jakovits, E. Vainikko, “Adapting scientific computing problems to clouds using mapreduce”, Future Generation Computer Systems 28 (1) (2012) 184 - 192.
[32] Jeffrey D. Ullman. 2012. Designing good MapReduce algorithms. XRDS 19, 1 (September 2012), 30-34.
[33] Saeed Maleki, Donald Nguyen, Andrew Lenharth, María Garzarán, David Padua, and Keshav Pingali. 2016. “DSMR: a shared and distributed memory algorithm for single-source shortest path problem”. SIGPLAN Not. 51, 8, Article 39 (February 2016), 2 pages
[34] Deepayan Chakrabarti and Christos Faloutsos. 2006. “Graph mining: Laws, generators, and algorithms”. ACM Comput. Surv. 38, 1, Article 2 (June 2006).
[35] David A. Bader and Kamesh Maddure. “Design and implementation of the hpcs graph analysis benchmark on symmetric multiprocessors”. In Proceedings of the 12th International Conference on High Performance Computing, HiPC'05, pages 465-476, Berlin, Heidelberg, 2005, Springer-Verlag.