Spark: Jaka jest złożoność czasu algorytmu połączonych komponentów używanego w GraphX?

Question

GraphX ​​zawiera algorithm for finding connected components wykresu.

Nie znalazłem oświadczenia o złożoności ich realizacji.

Zasadniczo wyszukiwanie podłączonych komponentów może odbywać się w czasie liniowym, na przykład przez pierwsze lub pierwsze wyszukiwanie według głębokości (patrz Wikipedia article). Jednakże zakłada to, że wykres można przechowywać w pamięci. GraphX ​​implementuje rozproszony algorytm poza rdzeniem, więc zakładam, że nie jest on porównywalny.

Czy wiesz, jak działa ich algorytm i jaka jest złożoność?

Answer 1

Uważam, że głównym celem wykresu w porównaniu do rozwiązania nie graficznego jest zmniejszenie liczby kolejnych kroków wymaganych do rozwiązania problemu. Różni się to od złożoności - w rzeczywistości rozwiązanie Graph może wymagać więcej instrukcji procesora, ale nadal jest właściwym rozwiązaniem, jeśli zmniejsza liczbę kolejnych kroków.

Pod względem wyszukiwania podłączonych komponentów, zarówno podejścia w zakresie szerokości i głębokości mają tę samą liczbę kolejnych kroków - to jest pewną wielokrotność liczby wierzchołków na wykresie. Ta sama logika musi być stosowana sekwencyjnie do każdego wierzchołka. To całe rozwiązanie.

Nawet jeśli twój wykres ma dwa mniej lub bardziej równe klastry, nie możesz podzielić pracy na dwóch pracowników i zacząć od jednego końca i spotkać się w środku. Nie wiesz, gdzie są końce. Nie wiesz, gdzie jest środek.

Jeśli wiedziałeś, że wchodzisz w to, co znasz, Twoja całkowita liczba kolejnych kroków może zostać zmniejszona do połowy. Jeśli to pomaga, możesz pomyśleć o tym, jako o teoretycznej jakości, którą możesz zrobić w kategoriach kolejnych kroków. I całkowicie zależy od kształtu wykresu.

Jeśli masz dużo dyskretnych klastrów, nie jest połączonych, a żaden klaster nie jest większy niż 10 osób, to teoretycznie najlepsze, co możesz zrobić, to 10 kolejnych kroków. Bez względu na to, ile masz mocy przetwarzania równoległego, najlepsze co możesz zrobić, to 10 kolejnych kroków.

Algorytm graficzny nie tylko przybliża Cię do teoretycznego minimum - w zależności od kształtu twoich gromad, faktycznie go bije.

Jak działa algorytm Spark? Jest to dość proste - każdy węzeł emituje tylko swoje sąsiadów, a jego sąsiedzi robią to samo. Dowolny węzeł, który otrzymuje niższą transmisję niż w następnej rundzie; jeśli nie, Vertex milczy.

Jeśli masz klastra, w którym każdy z wierzchołków jest połączony z każdym innym wierzchołkiem, to po jednej rundzie wiadomości każdy wie, kto jest najniższym VertexIDem, i wszyscy milkną w następnej rundzie. Jeden kolejny krok, cały klaster.

Jeśli, z drugiej strony, każdy wierzchołek w klastrze jest podłączony tylko do co najwyżej 2 innych wierzchołków, to może wykonać N kolejnych kroków, zanim wszystkie wierzchołki będą wiedzieć, co jest wartością minimalną VertexID.

Oczywiście kolejne kroki mają inny charakter w algorytmie wykresu, a nawet różnią się od wykresu do wykresu. Dobrze połączony wykres generuje dużo wiadomości i spędza więcej czasu na ich łączeniu itp. Nie zajmie to jednak tylu kroków sekwencyjnych, co mniej dobrze połączony wykres.

Krótko mówiąc, wydajność rozwiązania graficznego jest całkowicie zależna od kształtu wykresu, ale powinna zrównoleglić znacznie, znacznie lepiej niż rozwiązanie o szerokości lub głębokości.