Czy można zrobić PageRank bez całego zestawu danych?

Question

Przepraszam, jeśli to głupie, ale myślałem, że powinienem dać szansę. Powiedzmy, że mam ogromny wykres (na przykład 100 miliardów węzłów). Neo4J obsługuje 32 miliardy, a inne obsługują mniej więcej to samo, więc nie mogę mieć całego zestawu danych w bazie danych w tym samym czasie, czy mogę uruchomić pagerank, jeśli jest to skierowany wykres (bez pętli) i każdy zestaw węzłów łączy się do następnego zestawu węzłów (więc żadne nowe odsyłacze nie będą tworzone wstecz, tylko nowe łącza będą tworzone dla nowych zestawów danych).

Czy mogę jakoś wykorzystać wcześniejsze wyniki PageRank i zastosować je do nowych zestawów danych (zależy mi tylko na PageRank przy najnowszym zestawie danych, ale muszę mieć pagerank z poprzedniego zestawu, aby wyprowadzić dane ostatniego zestawu)?

Czy to ma sens? Jeśli tak, czy można to zrobić?

Answer 1

Należy obliczyć zasadniczy wektor własny na matrycy o wartości 100 miliardów na 100 miliardów. O ile nie jest to wyjątkowo rzadkie, nie można go dopasować wewnątrz urządzenia. Potrzebny jest więc sposób obliczenia wiodącego wektora własnego matrycy, kiedy można spojrzeć tylko na niewielką część macierzy naraz.

Metody iteracyjne do obliczania wektorów własnych wymagają tylko przechowywania kilku wektorów w każdej iteracji (każdy z nich ma 100 miliardów elementów). Te mogą pasować do twojej maszyny (4-bajtowe pływaki potrzebują około 375GB na wektor). Kiedy już masz wektor kandydatów do rankingowania, możesz (bardzo powoli) zastosować do niego swoją gigantyczną matrycę, czytając macierz w porcjach (ponieważ możesz spojrzeć na 32 miliardy wierszy naraz, będziesz potrzebować nieco ponad 3 porcje). Powtórz ten proces, a będziesz miał podstawy metody mocy, która jest używana w PageRank. cf http://www.ams.org/samplings/feature-column/fcarc-pagerank i

Oczywiście czynnikiem ograniczającym jest to, ile razy trzeba zbadać matrycę. Okazuje się, że przechowując więcej niż jeden wektor kandydata i stosując losowe algorytmy, można uzyskać dobrą dokładność przy mniejszej liczbie odczytów danych. Jest to aktualny temat badań w stosowanym świecie matematyki. Możesz znaleźć więcej informacji tutaj http://arxiv.org/abs/0909.4061, tutaj http://arxiv.org/abs/0909.4061, a tutaj http://arxiv.org/abs/0809.2274. Tutaj jest kod: http://code.google.com/p/redsvd/, ale nie możesz po prostu użyć tego gotowego do użycia wymiaru danych, o którym mówisz.

Innym sposobem, w jaki możesz to zrobić, jest sprawdzenie "przyrostowego dysku", który może lepiej pasować do Twojego problemu, ale jest nieco bardziej skomplikowany. Rozważmy następującą notatkę: http://www.cs.usask.ca/~spiteri/CSDA-06T0909e.pdf i to forum: https://mathoverflow.net/questions/32158/distributed-incremental-svd