Эффективный способ сохранить график для вычисления в Hadoop
Я в настоящее время пытаюсь выполнить вычисления как коэффициент кластеризации на огромных графиках с помощью Hadoop. Поэтому мне нужен эффективный способ сохранить график способом, что я могу легко получить доступ к узлам, их соседям и соседям соседей. График довольно редок и сохранен в разделенном файле огромной вкладки, где первое поле является узлом, от которого край переходит к второму узлу в поле два.
Заранее спасибо!
2 ответа
Проблема с сохранением графика непосредственно в HDFS заключается в том, что у вас нет средств для произвольного чтения данных. Итак, чтобы найти всех соседей узла, вам нужно обработать весь список ребер в HDFS, чтобы найти узлы, которые к нему подключены.
Таким образом, чтобы выполнить расчет коэффициента кластеризации, вам нужно дважды передать все данные. Первый раз находим узлы, которые подключены к стартовому узлу. Второй раз, чтобы узнать, как эти узлы связаны друг с другом.
Следовательно, каждый раз, когда вы хотите выйти на другой уровень в вашем графике, вам нужно будет обработать весь график, чтобы найти новые соединения.
Это легко сделать, ну да, это так. Эффективно ли время? Это действительно зависит от того, насколько быстро вы хотите иметь возможность вычислять такие вещи, как LCC, и насколько велик ваш график на самом деле. Это не будет и близко к реальному времени.
Другим подходом было бы использование HBase для хранения ваших ребер каким-либо образом, это дало бы вам произвольный доступ к узлам по-прежнему в параллельном режиме. В конце концов, HBase является частью hadoop.
Что-то, что может быть интересно, если вы хотите хранить большие графы параллельно, может быть FlockDB . Это база данных распределенных графов, недавно выпущенная Twitter. Я не использовал его, но, возможно, стоит взглянуть.
Если вы хотите делать это на индивидуальной основе, HBase / Cassandra может работать. Сохраните края в семействе столбцов: user_a_id - это ключ строки, user_b_id - ключи столбца (с пустыми значениями). FlockDB не подходит (они явно называют «запросы обхода графа» нецелевыми)
. Если бы вы захотели вычислить коэффициент кластеризации по всему графу, то есть сделать один гигантский эффективный вычисления - я бы использовал Hadoop. С некоторыми оговорками (см. Ниже) вы можете сделать это довольно просто; в infochimps мы использовали Wukong для твиттер-графа с сильными ссылками с миллионами узлов + ребер.
Что не сработает, так это наивное выполнение двухэтапного поиска в ширину из каждого узла, если ваш набор данных имеет высокий перекос. Если подумать о графике следования Twitter: 1,7 миллиона человек, которые подписаны на @wholefoods, имеют 600 тысяч исходящих ребер, с которыми приходится бороться, на 1 триллион двух переходов. Использование сильных ссылок значительно упрощает эту задачу (значительно снижает перекос); в противном случае сделайте некоторую частичную кластеризацию и повторите.