Получает ли секционированный граф результат алгоритма секционирования HDRF, хуже производительность при применении к графическому алгоритму в GraphX? - PullRequest
Новая
       18

Получает ли секционированный граф результат алгоритма секционирования HDRF, хуже производительность при применении к графическому алгоритму в GraphX?

0 голосов
/ 26 июня 2019

Кто-нибудь экспериментировал с запуском алгоритма графа (например, подсчет треугольников) после разбиения графа с помощью PartitionStrategy в Apache Spark GraphX?Мне интересно, почему выполнение во время выполнения алгоритма подсчета треугольников в секционированном графе, полученном в результате алгоритма HDRF (высокая степень репликации), хуже по сравнению с секционированным графом из RandomVertexCut в Apache Spark GraphX?

Итак, я сделалАлгоритм HDRF, кроме реализации Spark (я сделал это с C ++), затем программа получает список ребер и для каждого ребра возвращает ребро с номером раздела.Затем в классе Spark PartitionStrategy я сделал новую реализацию, которая просто возвращает номер раздела вместе с каждым ребром.Затем я попытался запустить алгоритм подсчета треугольников из Spark GraphX, сравнил время выполнения между графами, разделенными с использованием HDRF и RandomVertexCut, и оказалось, что алгоритм подсчета треугольников работает медленнее в алгоритме HDRF по сравнению с RandomVertexCut.

Я немного запутался, потому что в этой статье http://midlab.dis.uniroma1.it/articoli/PQDKI15CIKM.pdf, указано, что HDRF заставляет алгоритм графов работать быстрее.Я понял, что в статье они использовали GraphLab вместо GraphX.Мне интересно, может ли разница в среде обработчика графиков привести к разнице в результате.

Вот мои примерные ребра в файле списка ребер, сгенерированном алгоритмом HDRF: 

1 2 0 
2 3 1

Примечание: 1 20 означает, что ребро (1,2) помещено в раздел 0.

Здесь я покажу некоторый код в моем PartitionStrategy.scala 

case object HDRF extends PartitionStrategy {
    override def getPartition(src: VertexId, dst: VertexId, numParts: PartitionID): PartitionID = {
      numParts
    }
  }

Так что после входа в метод getPartition оннемедленно вернет номер раздела вместе с ребром (например, ребро 1 2 0 вернет 0 из метода getPartition)

Я ожидал, что время выполнения алгоритма подсчета треугольников будет меньше после графа разбиения с HDRFалгоритм по сравнению с RandomVertexCut, но на самом деле он работает хуже.

Есть ли идеи, почему это происходит в Apache Spark GraphX, но не в GraphLab?

...