Алгоритм распределенного локального кластерного коэффициента (MapReduce/Hadoop)

Я применил парадигму MapReduce на основе локального алгоритма коэффициентов кластеризации. Однако я столкнулся с серьезными проблемами для больших наборов данных или конкретных наборов данных (высокая средняя степень node). Я попытался настроить мою платформу хаоса и код, однако результаты были неудовлетворительными (по меньшей мере). Нет, я обратил мое внимание на то, чтобы изменить/улучшить алгоритм. Ниже мой текущий алгоритм (псевдокод)

foreach(Node in Graph) {
  //Job1
  /* Transform edge-based input dataset to node-based dataset */

  //Job2
  map() {
   emit(this.Node, this.Node.neighbours) //emit myself data to all my neighbours
   emit(this.Node, this.Node) //emit myself to myself
  }

  reduce() {
    NodeNeighbourhood nodeNeighbourhood;
    while(values.hasNext) {
      if(myself)
        this.nodeNeighbourhood.setCentralNode(values.next) //store myself data
      else
        this.nodeNeighbourhood.addNeighbour(values.next)  //store neighbour data
    }

    emit(null, this.nodeNeighbourhood)
  }

  //Job3
  map() {
    float lcc = calculateLocalCC(this.nodeNeighbourhood)
    emit(0, lcc) //emit all lcc to specific key, combiners are used
  }

  reduce() {
    float combinedLCC;
    int numberOfNodes;
    while(values.hasNext) {
      combinedLCC += values.next;
    }

    emit(null, combinedLCC/numberOfNodes); // store graph average local clustering coefficient
  }
}

Немного подробнее о коде. Для ориентированных графов данные соседей ограничены идентификаторами целевых идентификаторов идентификаторов ID и OUT для node (для уменьшения размера данных), для неориентированного его идентификатора node ID и границ назначения. Буферы сортировки и слияния увеличены до 1,5 Гб, потоки слияния 80.

Хорошо видно, что Job2 является актуальной проблемой всего алгоритма. Он генерирует огромное количество данных, которые необходимо сортировать/копировать/объединять. Это в основном убивает производительность моего алгоритма для определенных наборов данных. Может ли кто-нибудь направить меня на то, как улучшить алгоритм (я думал о создании итеративного Job2 [ "обрабатывать" только M узлов из N на каждой итерации до тех пор, пока каждый node не будет "обработан" ], но я отказался от этой идеи для Теперь). На мой взгляд, должен быть уменьшен объем вывода Job2, чтобы избежать дорогостоящих процессов сортировки/слияния, которые убивают производительность.

Я также реализовал тот же алгоритм (3 Джобса, тот же "шаблон связи", также проблема "Job2" ) для платформы Giraph. Однако Giraph является платформой в памяти, и алгоритм для тех же "проблемных" наборов данных приводит к исключению OutOfMemoryException.

За любым комментарием, замечанием, рекомендацией я буду благодарен.

---

UPDATE

Я собираюсь изменить алгоритм "резко". Я нашел эту статью Подсчет треугольников.

Как только код будет реализован, я опубликую свое мнение здесь и более подробный код (если этот подход будет успешным).

---

UPDATE_2

В конце концов я закончил "модификацию" алгоритма NodeIterator ++ для моих нужд (документ Yahoo доступен по ссылке в статье). К сожалению, хотя я вижу улучшение производительности, конечный результат не так хорош, как я надеялся. Вывод, который я сделал, заключается в том, что доступный мне кластер слишком мал, чтобы сделать расчеты LCC применимыми для этих конкретных наборов данных. Поэтому вопрос остается, или, скорее, развивается. Знает ли кто-нибудь об эффективном распределенном/последовательном алгоритме вычисления LCC или треугольников с ограниченными ресурсами? (Ни в коем случае я не утверждаю, что алгоритм NodeIterator ++ плох, я просто утверждаю, что доступных мне ресурсов недостаточно).