Ulepszanie algorytmu BFS

W sobotę udało mi się wgrać ogromny plik do HDFS (czyli do systemu rozproszonego hadoop – o tym kiedy indziej). W każdym razie, udało się, plik tam jest i zdołałam go odpowiednio przetworzyć tak by był gotowy do użycia przez moje algorytmy.

Niestety okazało się, że mój pomysł na ulepszenie algorytmu BFS (ang. breadth-first search, czyli przeszukiwanie wszerz) nie jest taki prosty jak się spodziewałam. Można powiedzieć, że zwykły, sekwencyjny algorytm BFS przechodzi przez graf poziomami. Pierw mamy źródło, czyli pojedynczy wierzchołek od którego zaczynamy nasze przechodzenie. W kolejnym poziomie odwiedzamy wszystkie wierzchołki które są połączone krawędzią ze źródłem. W następnym poziomie odwiedzamy wierzchołki których jeszcze nie odwiedziliśmy, ale które są połączone krawędzią z tymi z poprzedniego poziomu. I tak po samo dno grafu.

Algorytm ten jest zawstydzająco prosty do napisania w środowisku rozproszonym (ang. embarrassingly parallel) , choć wolę określenie, że problem jest perfekcyjnie równoległy. Jest tak dlatego, że z łatwością możemy rozdzielić zadanie przeglądania tego samego poziomu między wieloma maszynami jednocześnie.

Problem polega na tym, że jeśli graf jest dość głęboki, czyli ma bardzo dużo poziomów, to my możemy działać równolegle tylko poziomami, będziemy musieli i tak wykonać wiele powtórzeń algorytmu żeby przejść cały graf.

Moim początkowym pomysłem na ulepszenie tego problemu w modelu MapRecuce było podzielenie grafu między wszystkie maszyny i przefiltrowanie danych. Gdy zbędne krawędzie (czyli takie które nie polepszają wyniku) odfiltruje się z grafu, będzie on wystarczająco mały by mieścił się w pamięci jednego komputera. Wtedy wykonanie algorytmu BFS będzie już dużo szybsze.

Nie wiem niestety jak sprytnie podzielić graf między wszystkie maszyny. Algortm BFS musi być przecież wykonywany poziomami, a wczytując graf nie znamy jego struktury. Jest on również zbyt duży żeby przechowywać go całego w pamięci i przeanalizować w jakiejś wstępnej fazie które wierzchołki są bliżej dna a które bliżej źródła…

Plan jest zatem taki by troszkę jeszcze poszukać pomysłów na ten temat, ale żeby nie siedzieć nad tym zbyt długo, bo problem wydaje się nietrywialny. Średnica grafu Wikipedii jest bardzo mała w porównaniu do liczby wierzchołków (11 vs 12.150.976) więc można sobie pozwolić na 11 iteracji algorytmu. Wtedy warto napisać w podsumowaniu, że nie znając średnicy grafu to piszemy się na pewne ryzyko, że program będzie działał długo.

Podsumowując, dziś zajmę się:

  • krótką analizą o tym czy BFS dla grafu bez wag da się jakoś przefiltrować, żeby można go było docelowo całego umieścić w pamięci jednej maszyny i szybko obliczyć
  • zajmę się również uruchomieniem BFS bez wag dla grafu Wikipedii dla Sparka
  • na koniec, jeśli w mojej analizie wyjdzie na to, że zbędnych krawędzi w grafie nie da się odfiltrować, zajmę się uruchomieniem BFS bez wag dla grafu Wikipedii przy pomocy klasycznego rozwiązania z iteracjami.

Do dzieła!

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