pagerank w map-reduce: zadanie zaliczeniowe

Spis treści

Termin zadania: 22 czerwiec 2014 godzina 23:55 (uwaga: nie przyjmujemy zadań wysłanych więcej niż 12 godzin po terminie; za opóźnienie do 12 godzin odejmujemy 1 punkt)

Wersja: $Rev: 213 $

Ostatnia modyfikacja treści: $Date: 2014-06-17 14:01:54 +0200 (Tue, 17 Jun 2014) $ (zmiana: poprawione verifyprograms.py; FAQ; darmowy amazon ec2 nie działa )

1 Wprowadzenie

PageRank jest miarą centralności oryginalnie stworzoną dla wyszukiwarek internetowych, ale z powodzeniem wykorzystywaną również do innych sieci. Celem naszego zadania jest zaimplementowanie PageRank w map-reduce i zmierzenie efektywności różnych sposobów optymalizacji tego algorytmu (a najlepiej—opracowanie własnych optymalizacji).

Jako zbioru testowego będziemy używać zbioru miliona piosenek, a dokładnie miary podobieństwa piosenek z serwisu Last.fm ( http://labrosa.ee.columbia.edu/millionsong/lastfm ). W zbiorze tym dla każdej piosenki \(i\) podanych jest kilka-kilkadziesiąt piosenek podobnych \(j\); dla każdej podobnej piosenki \(j\) podana jest miara podobieństwa \(w(i,j)\). Potraktujemy miary podobieństwa piosenek jako wagę krawędzi (uwaga: wbrew intuicyjnemu rozumieniu podobieństwa ten graf jest skierowany, tzn. \(w(i, j) \neq w(j,i)\).). Zmodyfikujemy definicję PageRank tak, by uwzględniać wagi (oraz, uwaga, mnożymy wartość pagerank przez \(N\), żeby prościej było interpretować wyniki) tzn.:

\(PR(i; 0) = 1\) (w pierwszym kroku wszystkie piosenki mają ten sam, jednostkowy page-rank)

\(PR(i; t+1) = 1-d + d \sum_{j: (j,i) \in E} \frac{PR(j; t) * w(j,i)}{\sum_{(j,k) \in E} w(j,k)}\) (w kolejnych krokach page-rank piosenki propaguje się do sąsiadów z wagą proporcjonalną do znanej miary podobieństwa \(w(j,i)\); d to współczynnik wygaszania algorytmu)

W powszechnej opinii MapReduce niezbyt dobrze nadaje się do implementacji algorytmów grafowych. Lin i Schatz w pracy "Design patterns for efficient graph algorithms in MapReduce" podają kilka generycznych sposobów optymalizacji algorytmów grafowych: użycie combinera; łączenie w mapperze (in-mapper combining); ograniczenie zaburzania grafu w fazach map i reduce (schimmy); i przypisywanie wierzchołków do węzłów po zakresach wartości (range partitioning). Prosimy o przetestowanie wydajności tych sposobów optymalizacji na zbiorze miliona piosenek.

2 Wejście i wyjście

Programy będą testowane automatycznie. Prosimy o ścisłe przestrzeganie podanej poniżej formy wejścia i wyjścia.

2.1 Sposób uruchomienia programu

2.1.1 Tryb weryfikacji (hadoop nie działa w oddzielnym procesie)

cd xx123456; ant clean; ant verify

./verify.sh iter d e katalog-wejściowy katalog-wyjsciowy

gdzie d to wspólczynnik wygaszania; e to minimalna miara podobieństwa między piosenkami którą będziemy brać pod uwagę (proszę odrzucać podobieństwa mniejsze niż e); iter to liczba iteracji algorytmu. Oba katalogi są w lokalnym systemie plików. Przed uruchomieniem obliczeń należy stworzyć lub wyczyścić katalog-wyjściowy.

2.1.2 Tryb wydajnosciowy (hadoop w oddzielnym procesie)

cd xx123456; ant clean; ant perf

./perf.sh iter d e katalog-wejściowy katalog-wyjsciowy

Parametry jak wyżej. Katalogi odwołują się do katalogów w HDFS. Przed uruchomieniem obliczeń należy stworzyć lub wyczyścić katalog-wyjściowy.

2.2 Wejście

Format pliku wejściowego (na wejściu będzie kilka-kilkadziesiąt tego typu plików):

id_wierzcholka1 id_sasiada11,podobienstwo,id_sasiada12,podobienstwo,...

id_wierzcholka2 id_sasiada21,podobienstwo,id_sasiada22,podobienstwo,...

Uwaga: pliki wejściowe są konwertowane bezpośrednio z http://labrosa.ee.columbia.edu/millionsong/sites/default/files/lastfm/lastfm_similars.db . To znaczy, że w plikach mogą być błędy, np. niektóre id_sasiada mogą nie występować jako id_wierzcholka; wasze programy muszą być odporne na takie błędy.

Przykładowy plik wejściowy: 

A B,0.4,C,0.1,
B A,0.5,
C A,1.0,

2.3 Wyjście

Każdy z plików wyjściowych zawiera obliczony PageRank dla kolejnych wierzchołków grafu w formacie <id wierzchołka> <obliczony PageRank>.

Wyjście odpowiadające przykładowemu wejściu dla d=0.8, e=0, iter=20: 

A	1.450849569460237
B	1.146990475941271
C	0.43674761004462104

3 Forma oddania zadania

Prosimy o oddanie pojedynczego pliku .zip zawierającego pojedynczy katalog odpowiadający loginowi (ab123456), a w nim następujące pliki:

  • kod źródłowy programu ze wszystkimi optymalizacjami
  • skrypty do uruchomienia programu w dwóch trybach (patrz poprzedni punkt)
  • krótki raport opisujący zastosowany algorytm, zastosowane techniki optymalizacji czasu działania oraz testy wydajnościowe każdej z technik

4 Kryteria oceny

  • maksimum to 10 pkt
  • poprawna równoległa implementacja algorytmu page-rank: 5 pkt (rozwiązania niepoprawne nie dostają punktów za kolejne kategorie ).
  • zaimplementowanie i pomiar wydajności (czas wykonania) następujących optymalizacji (po 1 punkcie za każdą, zobacz artykuł Lin, Schatz):
    • ograniczenie użycia toString pomiędzy fazami map i reduce (jeśli podstawowe rozwiązanie używa toString)
    • combiner
    • combiner w fazie map (in-mapper combining)
    • schimmy
    • range partitioning
    • twoja optymalizacja
  • dodatkowe punkty za liczenie na amazon ec2 lub innej chmurze: 1-2 punkty (jeśli wykorzystujesz co najmniej 10 węzłów) (uwaga: amazon web services oferuje 750 godzin obliczeń za darmo dla nowo otwartych kont niestety darmowe instancje amazon ec2 mają za małą pamięci na uruchomienie hadoopa)

Wydajność prosimy liczyć dla (pod)zbiorów danych lastfm, dostępnych w katalogu students:/home/students/inf/PUBLIC/PWiR/last . Proszę korzystać z co najmniej 5 komputerów (jeśli przeprowadzasz obliczenia w laboratoriach MIM na kilka dni przed terminem, bądź miły dla innych i nie korzystaj z więcej niż 5 komputerów). Proszę korzystać z największego zbioru którego przetworzenie (10 iteracji algorytmu) zajmie najwyżej 10 minut. Proszę podawać wydajność nakładając kolejną optymalizację na poprzednią, tzn, np. wersja podstawowa 10 minut, wersja podstawowa + ograniczenie użycia toString 5 minut, wersja podstawowa + ograniczenie użycia toString + combiner 2 minuty.

Poprawność będziemy oceniać porównując wyniki implementacji z naszym rozwiązaniem wzorcowym; nasze testy biorą pod uwagę błędy zaokrągleń. Możecie ściągnąć niektóre z testów i program testowy z http://mimuw.edu.pl/~krzadca/verify-pagerank.tar.gz (parametry algorytmu: d=0.8, e=0, iter=20). Uwaga: będziemy oceniać poprawność ostatecznej wersji algorytmu (tzn. jeśli ktoś w raporcie opisuje optymalizacje range partitioning, to do sprawdzenia poprawności prosimy przygotować program który ma zaimplementowany range partitioning).

Za każde rozpoczęte 12 godzin spóźnienia odejmujemy 1 punkt.

Uwaga: ze względu na przedłużenie terminu zadania o tydzień NIE przyjmujemy zadań opóźnionych o więcej niż 12 godzin; za opóźnienie do 12 godzin odejmujemy 1 punkt.

5 Dodatkowe materiały

Prosimy o niekorzystanie z kodów źródłowych - gotowych implementacji algorytmu. Zalecamy natomiast przeczytanie następujących prac:

6 FAQ

  • dokładność numeryczna obliczeń

Proszę nie przejmować się dokładnością numeryczną.

  • budowanie programów

Proszę wzorować się na naszym skrypcie build.xml (do ściągnięcia z materiałami z laboratorium hadoopa). Czyli można założyć, że jar z dystrybucją hadoopa jest w ../hadoop-core-1.2.1.jar.

  • format wejścia: czy w plikach wejściowych mogą pojawić się dwa wiersze opisujące sąsiedztwo tego samego wierzchołka?

Nie.

Data: $Date: 2014-06-17 14:01:54 +0200 (Tue, 17 Jun 2014) $

Autor: Krzysztof Rządca

Created: 2014-06-17 Tue 14:02

Emacs 24.3.50.2 (Org mode 8.2.5h)

Validate