Idzie do przodu!

Powoli, powoli, idzie do przodu!

Co mam zrobione:

  • Algorytm BFS z iteracjami napisany w Hadoop dla grafu bez wag

Co się robi:

  • Algorytm Single Source Shortest Path w Spark z biblioteki GraphX dla grafu bez wag

Co potem:

  • Jak Spark skończy liczyć, będzie trzeba porównać wyniki i mam nadzieję, że będą identyczne! 🙂
  • Znaleźć info czy Spark potrafi policzyć SSSP dla grafu z wagami
  • Jeśli tak to policzyć powyższe a następnie przerobić algorytm Bfs na BfsWeighted żeby liczył BFS-a dla grafu z wagami

Inne algorytmy:

  1. Za pomocą algorytmu MST można zbadać połączone komponenty w grafie. Tak się składa, że GraphX zawiera w swojej bibliotece algorytm do zliczania połączonych komponentów. Należałoby zatem go uruchomić i sprawdzić jaki jest wynik oraz odpowiednio zaadaptować do tego MST – dzięki temu moje wypociny z tym algorytmem (któremu poświeciłam z dwa miesiące, kwiecień i maj) nie pójdą do kosza!
  2. W wolnym czasie można poczytać [1], jest tam trochę info o algorytmach które działają na systemach rozproszonych, a więc procesy nie dzielą wspólnej pamięci lecz przesyłają sobie wiadomości – czyli tak jak to działa w MapReduce. Warto by się wczytać na temat algorytmu APSP, może da się coś wykorzystać w oparciu o model MapReduce?
  3. Na końcu, jak już powyższe będzie policzone i ładnie zaprezentowane promotorowi, można się zająć algorytmami Triangle Count (opisanym w [2]), K-Means (szczegóły tu: [3]) oraz klasycznym dla MapReduce, algorytmem Page Rank. O szczegółach napiszę kiedy przyjdzie na to czas, teraz zajmę się poprzednimi punktami z listy.

______

[1] – M. Raynal, Distributed Algorithms for Message-Passing Systems, Chapter 2
[2] – Meysam Taassori , Counting Triangles in MapReduce
[3] – Weizhong Zhao, Huifang Ma and Qing He, Parallel K-Means Clustering Based on MapReduce, CloudCom 2009, LNCS 5931, pp. 674–679, 2009

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

w

Connecting to %s