Apache-Spark Графический кадр очень медленный на BFS

Question

Я использую Apache Spark-GraphFrames, используя Scala в следующем коде, я применяю BFS на приведенном выше коде и пытаюсь найти расстояние между Vertice 0 до 100.

import org.apache.spark._ 
import org.graphframes._ 
import org.graphframes.GraphFrame 
import org.apache.spark.sql.DataFrame 
import org.apache.spark.sql.SQLContext 
object SimpApp{ 
def main(args: Array[String]) { 
val conf = new SparkConf().setAppName("SimpApp") 
val sc = new SparkContext(conf) 
val sqlContext = new SQLContext(sc) 
val nodesList = sqlContext.read.format("com.databricks.spark.csv").option("header", "true").option("inferSchema", "true").load("CSV File Path") 
val edgesList= sqlContext.read.format("com.databricks.spark.csv").option("header", "true").option("inferSchema", "true").load("CSV File Path") 
val v=nodesList.toDF("id") 
val e=edgesList.toDF("src", "dst", "dist") 
val g = GraphFrame(v, e) 
var paths: DataFrame = g.bfs.fromExpr("id = 0").toExpr(s"id = 100").maxPathLength(101).run() 
paths.show() 
sc.stop() 
} 
} 

Soucre Node: 0 Destination Node: 100

Вершины Список приведен ниже

id 
0 
1 
2 
3 
. 
. 
. 
up to 
1000 

Вот список Edges

src dst dist 
0 1 2 
1, 2, 1 
2, 3, 5 
3, 4, 1 
4, 5, 3 
5, 6, 3 
6, 7, 6 
. . . 
. . . 
. . . 
up to 
999, 998, 4 

Но проблема с вышеуказанным кодом заключается в том, что он занимает большое количество времени только для выполнения для вершины от 0 до 100, поскольку он работал 4 часа, но нет выхода. Над кодом Я бегу на одиночной машине имеющей RAM 12 GB.

Не могли бы вы посоветовать мне ускорить и оптимизировать код.

Answer 1

Чтобы проверить, что вы пытаетесь найти кратчайшее расстояние для невзвешенных краев вашего графика, следовательно, использование BFS. В этих случаях, вы можете захотеть, чтобы удалить maxPathLength(101) из вашего запроса поэтому его:

g.bfs.fromExpr("id = 0").toExpr("id = 100").run() 

Как отмечался в BFS definition:

maxPathLength является ограничением по длине путей с дефолтом 10. Если не найдены допустимые пути длины < = maxPathLength, то BFS завершается.

Указывая 101 между вершиной 0 и вершиной 100, он попытается найти любые и все ребра от 0 до 100, которые имеют длину 101, следовательно, большое количество итераций.

Веселый пример BFS и кратчайшее расстояние можно описать в классическом графическом сценарии относительно полетов (ref: On-Time Flight Performance with GraphFrames for Apache Spark), где вершины (или узлы) являются аэропортами, а краями являются полеты между этими аэропортами.

Если вы пытаетесь найти беспосадочный рейс между SFO (Сан-Франциско) и BUF (Buffalo), запрос BFS будет:

tripGraph.bfs.fromExpr("id = 'SFO'").toExpr("id = 'BUF').maxPathLength(1).run 

, который, как указано в указанной ссылке, там нет прямых рейсов, следовательно никаких результатов. Но если увеличить maxPathLength на 2 (т.е. то есть один дополнительный узел между SFO и BUF узлов), то вы найдете множество пути (например SFO>BOS>BUF или Сан-Франциско в Бостон Буффало)

tripGraph.bfs.fromExpr("id = 'SFO'").toExpr("id = 'BUF').maxPathLength(2).run