research-article

Improving the shortest path finding algorithm in apache spark graphX

Authors:

Trung Phan,

Phuc DoAuthors Info & Claims

ICMLSC '18: Proceedings of the 2nd International Conference on Machine Learning and Soft Computing

Pages 67 - 71

https://doi.org/10.1145/3184066.3184083

Published: 02 February 2018 Publication History

Get Access

Abstract

The shortest path finding problem is one of the most important and common problems on graphs. It is also a basic problem applied to solve other problems such as the betweenness centrality problem, the closeness centrality problem... Therefore, in all graph processing platforms, there is a way to solve this problem. Apache Spark GraphX is also. However, the shortest path finding algorithm in GraphX has some drawbacks to discuss more. Therefore, in this paper we analyze some issues in finding the shortest path in GraphX, then we propose two new algorithms to improve for better performance, and finally we compare the performance between the shortest path finding algorithm in GraphX and proposed algorithms.

References

[1]

Rindra R., Apache Spark Graph Processing, 1st ed., BIRMINGHAM - MUMBAI: Packt Publishing, 2015.

Digital Library

Google Scholar

[2]

Karau H., Konwinski A., Wendell P., Zaharia M., Learning Spark, Sebastopol: O'Reilly Media, Inc, 2015.

Google Scholar

[3]

Min C., Shiwen M., Yunhao L., "Big Data: A Survey," Springer Science, 2014.

Google Scholar

[4]

Sabia J., Love A., "Technologies to Handle Big Data: A Survey," 2014.

Google Scholar

[5]

Michael S.M., Robin E., Spark GraphX in Action, New York: Manning Publications Co., 2016.

Digital Library

Google Scholar

[6]

Krishna S., Fast Data Processing with Spark 2 - Third Edition, Birmingham: Packt Publishing Ltd., 2016.

Digital Library

Google Scholar

[7]

Apache Spark API, "Apache Spark API - Scala," 2017. {Online}. Available: http://spark.apache.org/docs/latest/api/scala/#package. {Accessed 20 8 2017}.

Google Scholar

[8]

Ahmed O., Fatima-Zahra B., Ayoub A. L., Samir B., "Big Data technologies: A survey," Journal of King Saud University - Computer and Information Sciences, 2017.

Google Scholar

[9]

Apache Spark Cluster, "Cluster Mode Overview," 2017. {Online}. Available: https://spark.apache.org/docs/latest/cluster-overview.html. {Accessed 20 08 2017}.

Google Scholar

Cited By

View all

Theodorakopoulos LKarras ATheodoropoulou AKampiotis G(2024)Benchmarking Big Data Systems: Performance and Decision-Making Implications in Emerging TechnologiesTechnologies10.3390/technologies1211021712:11(217)Online publication date: 3-Nov-2024
https://doi.org/10.3390/technologies12110217
Alazzam HAbuAlghanam OSharieh A(2021)Best path in mountain environment based on parallel A* algorithm and Apache SparkThe Journal of Supercomputing10.1007/s11227-021-04072-078:4(5075-5094)Online publication date: 15-Sep-2021
https://doi.org/10.1007/s11227-021-04072-0

Index Terms

Improving the shortest path finding algorithm in apache spark graphX
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Shortest paths

Recommendations

A Multiple Pairs Shortest Path Algorithm

The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...
Performance comparison of Apache Hadoop and Apache Spark
ICAICR '19: Proceedings of the Third International Conference on Advanced Informatics for Computing Research

The term 'Big Data' is a broad term used for the data sets, which is enormous and traditional data processing applications find it hard to process. Both Apache Spark and Apache Hadoop are one of the significant parts of the big data family. Some of the ...
Finding min-sum disjoint shortest paths from a single source to all pairs of destinations
TAMC'06: Proceedings of the Third international conference on Theory and Applications of Models of Computation

Given a graph G = (V, E) with |V| = n, |E| = m, and a source node s, we consider the problem of finding two disjoint paths from s to two destination nodes t₁ and t₂ with minimum total length, for every pair nodes t₁, t₂ ∈ V–{s}. One efficient solution ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICMLSC '18: Proceedings of the 2nd International Conference on Machine Learning and Soft Computing

February 2018

198 pages

ISBN:9781450363365

DOI:10.1145/3184066

Conference Chairs:
Pham The Bao
University of Science, Vietnam
,
Genci Capi
Hosei University, Japan

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 February 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICMLSC 2018

ICMLSC 2018: ICMLSC 2018, The 2nd International Conference on Machine Learning and Soft Computing

February 2 - 4, 2018

Phu Quoc Island, Viet Nam

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
294
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Theodorakopoulos LKarras ATheodoropoulou AKampiotis G(2024)Benchmarking Big Data Systems: Performance and Decision-Making Implications in Emerging TechnologiesTechnologies10.3390/technologies1211021712:11(217)Online publication date: 3-Nov-2024
https://doi.org/10.3390/technologies12110217
Alazzam HAbuAlghanam OSharieh A(2021)Best path in mountain environment based on parallel A* algorithm and Apache SparkThe Journal of Supercomputing10.1007/s11227-021-04072-078:4(5075-5094)Online publication date: 15-Sep-2021
https://doi.org/10.1007/s11227-021-04072-0

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A Multiple Pairs Shortest Path Algorithm

Performance comparison of Apache Hadoop and Apache Spark

Finding min-sum disjoint shortest paths from a single source to all pairs of destinations