SYSTEM FOR DETECTING THE SHORTEST PATH BETWEEN MULTIPLE NODES IN REAL-TIME BASED ON LAMBDA ARCHITECTURE
DOI:
https://doi.org/10.24867/05BE17GrubisicKeywords:
shortest path, dynamic graph, Lambda Architecture, Spark, big dataAbstract
In this paper, we present the system for finding the shortest path between multiple nodes in a dynamic graph. The system is based on the Lambda Architecture. Modules for batch and real-time processing are implemented in Apache Spark. Besides this, we implemented a module for visualization by using Python Dash and a module for generating new weights on edges. The storage is built on top of the Hadoop Distributed File System and communication is based on the Kafka system for exchanging messages. All components are implemented in Python and executed inside Docker containers.
References
[1] „GoogleAI Graph Mining,“ https://ai.google/ research/teams/algorithms-optimization/graph-mining/. [8. 7. 2019.]
[2] A. Ching et al., „One Trillion Edges: Graph Processing at Facebook-Scale“, International Conference on Very Large Data Bases, 2015.
[3] N. Marz i J. Warren, Big Data Principles and Best Practices of Scalable Realtime Data Systems, Manning Publications, 2015.
[4] P. Hart, N. Nilsson i B. Raphael, „A Formal Basis for the Heuristic Determination of Minimum Cost Paths“. Computer Science and cybernetics,1968.
[5] R. Geisberger i P. Sanders, „Exact routing in large road networks using contraction hierarchies,“ u Transportation Science, 2012.
[6] L. Roditty i U. Zwick, „Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs“, SIAM Journal on Computing, 2012.
[7] M. Henzinger, S. Krinninger i D. Nanongkai, „Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization“, Annual Symposium on Foundations of Computer Science, 2013.
[8] „Apache Spark,“ https://spark.apache.org/, [24. 6. 2019.].
[9] „Dash User Guide,“, https://dash.plot.ly/, [24. 6. 2019.].
[10] „Docker,“, https://www.docker.com/, [24. 6. 2019.].
[2] A. Ching et al., „One Trillion Edges: Graph Processing at Facebook-Scale“, International Conference on Very Large Data Bases, 2015.
[3] N. Marz i J. Warren, Big Data Principles and Best Practices of Scalable Realtime Data Systems, Manning Publications, 2015.
[4] P. Hart, N. Nilsson i B. Raphael, „A Formal Basis for the Heuristic Determination of Minimum Cost Paths“. Computer Science and cybernetics,1968.
[5] R. Geisberger i P. Sanders, „Exact routing in large road networks using contraction hierarchies,“ u Transportation Science, 2012.
[6] L. Roditty i U. Zwick, „Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs“, SIAM Journal on Computing, 2012.
[7] M. Henzinger, S. Krinninger i D. Nanongkai, „Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization“, Annual Symposium on Foundations of Computer Science, 2013.
[8] „Apache Spark,“ https://spark.apache.org/, [24. 6. 2019.].
[9] „Dash User Guide,“, https://dash.plot.ly/, [24. 6. 2019.].
[10] „Docker,“, https://www.docker.com/, [24. 6. 2019.].
Downloads
Published
2019-11-03
Issue
Section
Electrotechnical and Computer Engineering
