Эффективный способ хранить график для расчета в Hadoop

Question

В настоящее время я пытаюсь выполнить вычисления, такие как коэффициент кластеризации на огромных графиках, с помощью Hadoop. Поэтому мне нужен эффективный способ хранения графа таким образом, чтобы я мог легко получить доступ к узлам, их соседям и соседям соседей. График довольно разреженный и хранится в огромном файле, разделенном табуляцией, где первое поле - это узел, от которого ребро переходит ко второму узлу в поле два.

Заранее спасибо!

Answer 1

Если вы хотите сделать это для каждого пользователя, HBase / Cassandra может работать. Сохраните ребра в семействе столбцов: user_a_id - ключ строки, user_b_id - ключи столбца (с пустыми значениями). FlockDB не очень подходит (они явно ссылаются на «ходящие по графику запросы» как нецелевые)

Если бы вы хотели рассчитать коэффициент кластеризации по всему графику, то есть выполнить одно гигантское эффективное вычисление, я бы использовал Hadoop. С некоторыми оговорками (см. Ниже) вы можете сделать это довольно просто; на infochimps мы использовали Wukong на твиттер-графе с сильными ссылками с миллионами узлов + ребер.

Что не сработает, так это наивно выполнять поиск в два шага в ширину из каждого узла, если ваш набор данных имеет высокий перекос. Думая о Twitter, следуйте за графиком: 1,7 миллиона людей, которые следят за @wholefoods, имеют 600 000 исходящих граней, за которые нужно бороться, за 1 триллион 2 прыжков. Использование сильных ссылок делает это намного проще (значительно уменьшает перекос); в противном случае выполните частичную кластеризацию и выполните итерацию.

Answer 2

Проблема с хранением графика непосредственно в HDFS заключается в том, что у вас нет средств для случайного чтения данных. Поэтому, чтобы найти всех соседей узла, вам нужно обработать весь список ребер в HDFS, чтобы найти узлы, которые к нему подключены.

Таким образом, чтобы выполнить расчет коэффициента кластеризации, вам нужно будет дважды передать все данные. Первый раз найти узлы, которые подключены к начальному узлу. Второй раз выяснить, как эти узлы связаны друг с другом.

Каждый раз, когда вы хотите выйти на другой уровень в вашем графике, вам нужно будет обработать весь график, чтобы найти новые соединения.

Это легко сделать, да, это так. Это время эффективно? Это действительно зависит от того, насколько быстро вы захотите рассчитывать такие вещи, как LCC, и насколько велик ваш график. Это не будет близко к реальному времени.

Другой подход заключается в использовании HBase для хранения ваших ребер каким-либо образом, это даст вам произвольный доступ к узлам, все еще параллельным. Ведь HBase является частью hadoop.

Что-то, что может представлять интерес, если вы хотите хранить большие графы в параллельном режиме, может быть FlockDB . Это распределенная графовая база данных, недавно выпущенная Twitter. Я не использовал это, но это могло бы стоить посмотреть.