W jaki sposób pagerank jest obliczany w sposób rozproszony?

Question

Rozumiem ideę pagerank i zaimplementowałem ją (czytając książkę "programowanie inteligencji zbiorowej").

Ale czytałem, że może być rozpowszechniany na wielu serwerach (jak sądzę, Google robi). Jestem nieco zdezorientowany, ponieważ zgodnie z moim rozumowaniem potrzebowałeś całego wykresu, aby zrobić ranking strony, ponieważ każdy ranking był względny w stosunku do innych rankingów.

Znalazłem wiki article, ale nie wyjaśniłem wiele.

Jakieś sugestie, jak to jest możliwe? Ponadto pytanie premiowe: czy technika rozprowadzania pageranku jest dostępna wyłącznie na PageRank, czy też zastosowana metoda może być zastosowana do innych algorytmów uczenia maszynowego zastosowanych do wykresów?

Answer 1

Podstawowym sposobem obliczania PageRank jest struktura Google Pregel. Jestem prawie pewien, że mają teraz coś bardziej wyrafinowanego, ale to jest ostatni opublikowany wysiłek.

Możesz przeczytać więcej szczegółów na ten temat w research blog. Lub przeczytaj opublikowany artykuł here.

Pracuję nad wersją Open Source Bulk Synchronous Parallel paradygmatu o nazwie Apache Hama. Istnieje również Apache Giraph, który koncentruje się wyłącznie na zastosowaniach graficznych i wielu innych.

Tak jak wspomniane mfrankli, istnieje również framework MapReduce (na przykład Apache Hadoop), który może być użyty do obliczenia PageRank, ale nie jest wydajny w przypadku iteracyjnych algorytmów.

Warto dodać, że oba rozwiązania (MapReduce i BSP) to rozwiązania wsadowe, więc można je wykorzystać do ponownego obliczenia PageRank dla całego webgraphu. Ponieważ aktualizacje Google są znacznie szybsze niż algorytmy wsadowe, możesz się spodziewać, że często przeliczają one PageRank na podgraphach.

Answer 2

MapReduce zapewnia pewne interesujące tło i może wyjaśnić, w jaki sposób zrównoleglimy to zadanie.