Ist es möglich, den All-Pairs-Algorithmus für den kürzesten Pfad mit parallelem Framework in einem großen Graphen zu implementieren?

Question

Mit Spark graphx pregel api ist es einfach zu berechnen einzigen Quelle kürzesten Weg in großen Graphen, zum Beispiel Millionen Ecken und Zehn Millionen Kanten, mit akzeptabler Laufzeit, zum Beispiel mehrere Stunden. Aber ist es möglich, den kürzesten Pfad aller Paare in einem großen Graphen in akzeptabler Laufzeit auszuführen?

Answer 1

Graphen mit Millionen von Vertices können leicht auf einer einzigen Maschine verarbeitet werden, solange es genügend Speicher hat, so dass es nicht notwendig ist, die Strafe durch Skalierung und viele moderne Bibliotheken zu bezahlen, sind stark optimiert und können modern nutzen Hardware.

Im Gegensatz dazu sind verteilte Lösungen normalerweise durch die Kommunikation zwischen den Knoten begrenzt, und exakte Algorithmen skalieren nicht gut. Es ist möglich, Dinge mit Näherungen und Heuristiken signifikant zu verbessern und a priori Wissen über die Struktur von Daten zu nutzen.

(Meinung Alarm) Persönlich würde ich meiden, so weit von möglich von Graph-Verarbeitung auf Spark-:

• GraphX ​​wurde vor effektiv Jahren aufgegeben. Es zeigt auch sehr schlechte Skalierungsfähigkeiten, nach Facebook's study
• Grapframes sind unreif und ineffizient.