GraphX kommt mit einem Algorithmus zum Finden von verbundenen Komponenten von a Grafik.
Ich habe keine Aussage über die Komplexität ihrer Implementierung gefunden.
Im Allgemeinen kann das Auffinden von verbundenen Komponenten in linearer Zeit erfolgen, z. B. durch eine Breitensuche oder Tiefensuche (siehe Wikipedia Artikel ). Dies setzt jedoch voraus, dass Sie den Graphen im Speicher behalten können. GraphX implementiert einen verteilten Out-of-Core-Algorithmus, also nehme ich an, dass er nicht vergleichbar ist.
Wissen Sie, wie ihr Algorithmus funktioniert und welche Komplexität vorliegt?
Ich behaupte, dass das Hauptziel einer Grafik gegenüber einer Nicht-Graph-Lösung darin besteht, die Anzahl der sequentiellen Schritte zu reduzieren, die zur Lösung des Problems erforderlich sind. Dies ist anders als die Komplexität - tatsächlich kann eine Graph-Lösung mehr CPU-Befehle insgesamt ausführen und dennoch die richtige Lösung sein, wenn sie die Anzahl der sequentiellen Schritte reduziert.
Hinsichtlich des Findens von verbundenen Komponenten weisen sowohl die Breiten- als auch die Tiefennäher-Ansätze die gleiche Anzahl von aufeinanderfolgenden Schritten auf - d. h. einige Vielfache der Anzahl von Eckpunkten in dem Graphen. Dieselbe Logik muss sequentiell auf jeden Knoten angewendet werden. Das ist die ganze Lösung.
Auch wenn Ihr Diagramm zwei mehr oder weniger gleich große Cluster enthält, können Sie die Arbeit nicht in zwei Worker aufteilen und an einem Ende beginnen und sich in der Mitte treffen. Du weißt nicht, wo die Enden sind. Du weißt nicht, wo die Mitte ist.
Wenn Sie wissen, was Sie wissen, wenn Sie herauskommen, könnte Ihre Gesamtanzahl der aufeinanderfolgenden Schritte auf die Hälfte reduziert werden. Wenn es hilft, können Sie darüber nachdenken, was das Beste ist, was Sie in Bezug auf sequenzielle Schritte tun können. Und es hängt vollständig von der Form Ihres Graphen ab.
Wenn Sie viele diskrete Cluster haben, die nicht angegliedert sind und kein Cluster größer als 10 Personen ist, dann ist das theoretisch Beste, was Sie tun könnten, 10 sequenzielle Schritte. Egal, wie viel Parallelverarbeitungsleistung Sie hatten, das Beste, was Sie tun können, sind 10 sequentielle Schritte.
Ein Graphalgorithmus bringt Sie nicht nur näher an das theoretische Minimum heran - abhängig von der Form Ihrer Cluster schlägt es tatsächlich.
Wie funktioniert der Spark-Algorithmus? Es ist ziemlich einfach - jeder Knoten sendet nur seine VertexId an seine Nachbarn, und seine Nachbarn tun das gleiche. Jeder Knoten, der ein VertexId niedriger als sein eigenes empfängt, sendet die nächste Runde; wenn nicht, wird der Vertex still.
Wenn Sie einen Cluster haben, in dem jeder der Eckpunkte mit jedem anderen Eckpunkt verbunden ist, dann weiß jeder nach einer Runde von Nachrichten, wer die niedrigste VertexID ist, und alle werden in der nächsten Runde still. Ein sequentieller Schritt, der gesamte Cluster.
Wenn andererseits jeder Scheitelpunkt im Cluster nur mit höchstens zwei anderen Scheitelpunkten verbunden ist, könnte es N sequenzielle Schritte erfordern, bevor alle Scheitelpunkte wissen, wer das minimale VertexID ist.
Offensichtlich sind die sequentiellen Schritte im Diagrammalgorithmus von unterschiedlicher Art und sogar von Diagramm zu Diagramm unterschiedlich. Ein gut verbundenes Diagramm erzeugt viele Nachrichten und verbraucht mehr Zeit, um sie zusammenzuführen usw. Aber es werden nicht so viele sequentielle Schritte wie bei einem weniger gut verbundenen Diagramm benötigt.
Lange Rede, kurzer Sinn, die Leistung der Graph-Lösung hängt vollständig von der Form des Graphen ab, aber sie sollte viel, viel besser parallel sein als eine Breiten- oder Tiefenlösung.
Tags und Links algorithm time-complexity apache-spark spark-graphx connected-components