Tato práce řeší problém hledání nejkratší cesty v silniční síti, kde doba průjezdu úsekem závisí na čase, konkrétně problém volby doby výjezdu pro dosažení nejkratšího času cesty. Cílem této práce je vyvinout a implementovat paralelní algoritmus. Zaměřil jsem se na algoritmus pro distribuované prostředí na bázi modelu MapReduce.
Práce představuje MapReduce algoritmus pracující ve spojitém čase a založený na LCA (Label Corecting Algorithm), který byl implementován v prostředí Apache Spark za pomocí nástavby GraphX určené pro grafové analýzy. Jako graf byla použita silniční síť z OSM a transportní funkce byly vygenerovány náhodně.
Byl navržen a implementován paralelní algoritmus se složitostí O(n^2) a dobrou škálovatelností. Dále byly provedeny výkonnostní testy, které ukázaly, že vyvinutý algoritmus je vhodný pro velmi velké grafy (které se nevejdou do paměti jednoho počítače), protože režie distribuovaného systému u malých grafů tvoří velké procento výpočetního času.
Annotation in English
This article deals with time-dependent shortest path problem. Concretely article is solving min-cost one-to-all problem. The intention of the article is implementation parallel algorithm for distributed environment based on MapReduce.
Article presents MapReduce algorithm, which works in continues time. The algorithm is based on LCA (Label Correcting Algorithm), which was implementing in Apache Spark environment using GraphX framework. Route network was used like input graph.
Final algorithm has complexity O(n^2) and has good scalability. They were made performance tests. Developed algorithm is suitable for large graphs. In small graphs distributed system spend a lot of time distributing data.
Keywords
Apache Spark, nejrychlejší cesta v grafu, časová závislost, distribuované prostředí, MapReduce
Tato práce řeší problém hledání nejkratší cesty v silniční síti, kde doba průjezdu úsekem závisí na čase, konkrétně problém volby doby výjezdu pro dosažení nejkratšího času cesty. Cílem této práce je vyvinout a implementovat paralelní algoritmus. Zaměřil jsem se na algoritmus pro distribuované prostředí na bázi modelu MapReduce.
Práce představuje MapReduce algoritmus pracující ve spojitém čase a založený na LCA (Label Corecting Algorithm), který byl implementován v prostředí Apache Spark za pomocí nástavby GraphX určené pro grafové analýzy. Jako graf byla použita silniční síť z OSM a transportní funkce byly vygenerovány náhodně.
Byl navržen a implementován paralelní algoritmus se složitostí O(n^2) a dobrou škálovatelností. Dále byly provedeny výkonnostní testy, které ukázaly, že vyvinutý algoritmus je vhodný pro velmi velké grafy (které se nevejdou do paměti jednoho počítače), protože režie distribuovaného systému u malých grafů tvoří velké procento výpočetního času.
Annotation in English
This article deals with time-dependent shortest path problem. Concretely article is solving min-cost one-to-all problem. The intention of the article is implementation parallel algorithm for distributed environment based on MapReduce.
Article presents MapReduce algorithm, which works in continues time. The algorithm is based on LCA (Label Correcting Algorithm), which was implementing in Apache Spark environment using GraphX framework. Route network was used like input graph.
Final algorithm has complexity O(n^2) and has good scalability. They were made performance tests. Developed algorithm is suitable for large graphs. In small graphs distributed system spend a lot of time distributing data.
Keywords
Apache Spark, nejrychlejší cesta v grafu, časová závislost, distribuované prostředí, MapReduce
Proveďte rešerši dostupných paralelních algoritmů pro hledání nejkratší trasy závislé na čase. Dále analyzujte dostupnost reálných dat souvisejících s problémem (např. data pro silniční síť). Data zpracujte a implementujte vybraný algoritmus pomocí modelu MapReduce. Na závěr proveďte testování a zhodnocení zvoleného řešení.
Research Plan
Proveďte rešerši dostupných paralelních algoritmů pro hledání nejkratší trasy závislé na čase. Dále analyzujte dostupnost reálných dat souvisejících s problémem (např. data pro silniční síť). Data zpracujte a implementujte vybraný algoritmus pomocí modelu MapReduce. Na závěr proveďte testování a zhodnocení zvoleného řešení.
Recommended resources
DING, B., Jeffrey X. Y. a QIN, L. Finding time-dependent shortest paths over large graphs. Proceedings of the 11th international conference on Extending database technology Advances in database technology - EDBT '08 [online]. 2008 [cit. 2014-09-24]. DOI: 10.1145/1353343.1353371.
AJI, A. WANG, F. VO, H. LEE, R. LIU, Q. ZHANG, X. SALTZ, J. Hadoop GIS. Proceedings of the VLDB Endowment [online]. 2013-08-27, vol. 6, issue 11, s. 1009-1020 [cit. 2014-09-24]. DOI: 10.14778/2536222.2536227.
CHABINI, I. GANUGAPATI, S. Parallel Algorithms for Dynamic Shortest Path Problems. International Transactions in Operational Research [online]. 2002, vol. 9, issue 3, s. 279-302 [cit. 2014-09-24]. DOI: 10.1111/1475-3995.00356.
KARAU, Holden. Fast data processing with Spark: high-speed distributed computing made easy with Spark. New Edition. Birmingham, UK: Packt Publishing, 2013. ISBN 17-821-6706-4.
CARY, Ariel, Zhengguo SUN, Vagelis HRISTIDIS a Naphtali RISHE. Experiences on Processing Spatial Data with MapReduce. [online]. s. 302 [cit. 2014-09-24]. DOI: 10.1007/978-3-642-02279-1_24.
SZKANDERA, Jakub. Navigace jedinců v rámci davů. Plzeň, 2012. Bakalářská práce. Západočeská univerzita v Plzni. Fakulta aplikovaných věd.
Recommended resources
DING, B., Jeffrey X. Y. a QIN, L. Finding time-dependent shortest paths over large graphs. Proceedings of the 11th international conference on Extending database technology Advances in database technology - EDBT '08 [online]. 2008 [cit. 2014-09-24]. DOI: 10.1145/1353343.1353371.
AJI, A. WANG, F. VO, H. LEE, R. LIU, Q. ZHANG, X. SALTZ, J. Hadoop GIS. Proceedings of the VLDB Endowment [online]. 2013-08-27, vol. 6, issue 11, s. 1009-1020 [cit. 2014-09-24]. DOI: 10.14778/2536222.2536227.
CHABINI, I. GANUGAPATI, S. Parallel Algorithms for Dynamic Shortest Path Problems. International Transactions in Operational Research [online]. 2002, vol. 9, issue 3, s. 279-302 [cit. 2014-09-24]. DOI: 10.1111/1475-3995.00356.
KARAU, Holden. Fast data processing with Spark: high-speed distributed computing made easy with Spark. New Edition. Birmingham, UK: Packt Publishing, 2013. ISBN 17-821-6706-4.
CARY, Ariel, Zhengguo SUN, Vagelis HRISTIDIS a Naphtali RISHE. Experiences on Processing Spatial Data with MapReduce. [online]. s. 302 [cit. 2014-09-24]. DOI: 10.1007/978-3-642-02279-1_24.
SZKANDERA, Jakub. Navigace jedinců v rámci davů. Plzeň, 2012. Bakalářská práce. Západočeská univerzita v Plzni. Fakulta aplikovaných věd.