SISTEM ZA PRONALAŽENJE NAJKRAĆE PUTANJE IZMEĐU LOKACIJA SA TEŽINAMA PUTANJA PROMENLJIVIM U REALNOM VREMENU ZASNOVAN NA ARHITEKTURI LAMBDA
Ključne reči:
najkraća putanja, dinamički graf, arhitektura Lambda, Spark, veliki skupovi podataka
Apstrakt
U ovom radu predstavljen je sistem za pronalaženje najkraće putanje između više čvorova u grafu sa promenljivim težinama grana, zasnovan na arhitekturi Lambda. Moduli za paketnu obradu i obradu u realnom vremenu implementirani su u tehnologiji Spark. Realizovani su takođe i modul za vizuelizaciju, uz upotrebu Pajton biblioteke Daš, i modul za generisanje novih težina u grafu. Skladište podataka se zasniva na distribuiranom fajl sistemu Hadup, a komunikacija između modula ostvarena je korišćenjem sistema za razmenu poruka Kafka. Sve komponente implementirane su u programskom jeziku Pajton i izvršavaju se unutar kontejnera tehnologije Doker.
Reference
[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.].
Objavljeno
2019-11-03
Sekcija
Elektrotehničko i računarsko inženjerstvo
