Rozproszony algorytm współczynnika lokalnego skupiania (MapReduce/Hadoop)

Question

Zaimplementowałem model oparty na MapReduce oparty na local clustering coefficient algorithm. Jednak napotkałem poważne problemy w przypadku większych zestawów danych lub określonych zestawów danych (wysoki średni stopień węzła). Próbowałem dostroić moją platformę hadoop i kod, jednak wyniki były niezadowalające (co najmniej). Nie. Zwróciłem moją uwagę na faktyczną zmianę/ulepszenie algorytmu. Poniżej znajduje się mój aktualny algorytm (pseudo kod):

foreach(Node in Graph) { 
    //Job1 
    /* Transform edge-based input dataset to node-based dataset */ 

    //Job2 
    map() { 
    emit(this.Node, this.Node.neighbours) //emit myself data to all my neighbours 
    emit(this.Node, this.Node) //emit myself to myself 
    } 

    reduce() { 
    NodeNeighbourhood nodeNeighbourhood; 
    while(values.hasNext) { 
     if(myself) 
     this.nodeNeighbourhood.setCentralNode(values.next) //store myself data 
     else 
     this.nodeNeighbourhood.addNeighbour(values.next) //store neighbour data 
    } 

    emit(null, this.nodeNeighbourhood) 
    } 

    //Job3 
    map() { 
    float lcc = calculateLocalCC(this.nodeNeighbourhood) 
    emit(0, lcc) //emit all lcc to specific key, combiners are used 
    } 

    reduce() { 
    float combinedLCC; 
    int numberOfNodes; 
    while(values.hasNext) { 
     combinedLCC += values.next; 
    } 

    emit(null, combinedLCC/numberOfNodes); // store graph average local clustering coefficient 
    } 
} 

Nieco więcej szczegółów na temat kodu. W przypadku skierowanych wykresów dane sąsiadów są ograniczone do identyfikatorów węzła i ID docelowych krawędzi OUT (w celu zmniejszenia rozmiaru danych), w przypadku nieukierunkowanych to również identyfikator węzła i identyfikatory docelowe krawędzi. Bufory sortowania i łączenia zwiększają się do 1,5 Gb, łączą strumienie 80.

Widać wyraźnie, że Job2 jest rzeczywistym problemem całego algorytmu. Generuje ogromną ilość danych, które muszą być posortowane/skopiowane/połączone. To w zasadzie zabija moją wydajność algorytmu dla niektórych zestawów danych. Czy ktoś może mnie poprowadzić jak poprawić algorytm (myślałem o stworzeniu iteracyjnego Job2 ["proces" tylko M węzłów z N w każdej iteracji, aż każdy węzeł zostanie "przetworzony"], ale na razie porzuciłem ten pomysł) . Moim zdaniem wydruk mapy Job2 powinien zostać zmniejszony, aby uniknąć kosztownych procesów sortowania/scalania, które zabijają wydajność.

Zaimplementowałam również ten sam algorytm (3 zadania, ten sam wzorzec komunikacji, także problem "Job2") dla platformy Giraph. Jednak Giraph jest platformą w pamięci, a algorytm dla tych samych "problematycznych" zestawów danych powoduje wyjątek OutOfMemoryException.

Za każdą uwagę, uwagę, wytyczną będę wdzięczny.

---

UPDATE

Zamierzam zmienić algorytm "drastycznie". Znalazłem ten artykuł Counting Triangles.

Po wprowadzeniu kodu opublikuję tutaj moją opinię i bardziej szczegółowy kod (jeśli to podejście zakończy się powodzeniem).

---

UPDATE_2

W końcu mam zakończony „Zmiana” NodeIterator ++ algorytm do moich potrzeb (papier Yahoo jest dostępna za pośrednictwem linku w artykule). Niestety, mimo że widzę poprawę wydajności, wynik końcowy nie jest tak dobry, jak się spodziewałem. Doszedłem do wniosku, że dostępny dla mnie klaster jest po prostu zbyt mały, aby umożliwić wykonanie obliczeń LCC dla tych konkretnych zestawów danych. Pytanie pozostaje, a raczej ewoluuje. Czy ktoś wie o skutecznym algorytmie rozproszonym/sekwencyjnym do obliczania LCC lub trójkątów z ograniczonymi dostępnymi zasobami? (W żadnym wypadku nie stwierdzam, że algorytm NodeIterator ++ jest zły, po prostu stwierdzam, że zasoby, które są dla mnie dostępne, są po prostu niewystarczające).

Answer 1

W artykule "MapReduce in MPI for large graph algorithms" autorzy podają ładny opis implementacji MapReduce zliczania trójkątów. Artykuł jest dostępny tutaj: http://www.sciencedirect.com/science/article/pii/S0167819111000172, ale do uzyskania dostępu do papieru może być potrzebne konto. (Jestem na systemie uniwersyteckim, który jest opłacany za subskrypcję, więc nigdy nie wiem, do czego mam dostęp tylko dlatego, że już zapłacili.) Autorzy mogą mieć szkic artykułu opublikowanego na osobistej stronie (stronach).

Jest jeszcze jeden sposób, w jaki można policzyć trójkąty - prawdopodobnie o wiele mniej wydajne, chyba że wykres jest dość gęsty. Najpierw skonstruuj macierz sąsiedztwa swojego wykresu, A. Następnie obliczyć A^3 (można bardzo łatwo wykonać równoległe zwielokrotnienie macierzy). Następnie podsumuj (i, i) wpisy A^3 i podziel odpowiedź przez 6. To da ci liczbę trójkątów, ponieważ pozycja I, j A^k zlicza długość k spacerów od i do j, a ponieważ patrzymy tylko na długość 3 spacerów, każdy spacer, który zaczyna się na i i kończy na i po 3 krokach, jest trójkątem ... liczącym ponad 6 razy. Jest to głównie mniej efektywne, ponieważ rozmiar matrycy będzie bardzo duży w porównaniu do rozmiaru arkusza edgelistycznego, jeśli wykres jest niewielki.