Как обрабатывать вершины с большим количеством ребер? - PullRequest
Новая
       108

Как обрабатывать вершины с большим количеством ребер?

0 голосов
/ 15 января 2019

В нашем графе есть много вершин, которые имеют более 100 000 исходящих ребер. Я хотел бы знать, каковы подходы, чтобы справиться со всеми палитрами ситуаций, которые вытекают из этого.

Допустим, у нас есть group_1, определенный на нашем графике. group_1 имеет 100k members. У нас есть несколько обходов, которые начинаются с вершины member_x и вычисляют некоторые вещи. Эти обходы довольно быстрые, они заканчиваются в течение ~ 2 с каждый.

Но времена изменились, и теперь у нас есть требование объединить все результаты отдельных небольших обходов в одно число. Обходы должны содержать все результаты от group_1 участников.

Сначала наш подход заключался в создании обходов, которые генерируют пакет members_x, используя skip и limit, а затем, используя параллельную обработку на уровне приложения, подсчитывают сумму наших вещей. Однако у этого подхода есть несколько проблем:

  • g.V().has('group',y).out('member_of').skip(0).limit(10) - согласно документации этот обход может каждый раз возвращать разные результаты. Так что создание пакетов таким способом было бы некорректно
  • g.V().has('group',y).out('member_of').skip(100_000).limit(10) занимает слишком много времени, потому что, как мы выяснили, базе данных все равно придется посещать 100 тыс. Вершин

Итак, наш следующий подход - сохранить обход, который генерирует пакеты members, а затем в отдельных потоках выполнить параллельные обходы, которые подсчитывают сумму по ранее выбранному элементу: 

while(is_not_the_end) {
   List<Members> members = g.V().has('group',y).out('member_of').next(100)`
   addMembersToExecutorThread(members) // done in async way
}

Итак, каковы подходы, когда у вас есть такие сценарии? По сути, мы можем решить эту проблему, если найдется способ быстро выбрать всех предков какой-либо вершины. В нашем случае это будет group_1. Но для извлечения идентификаторов требуется много времени, используя g.V().has('group',y).out('member_of').properties('members_id').

Есть ли способ обойти эту проблему? Или, может быть, мы должны попытаться выполнить такие запросы на GraphComputer?

1 Ответ

0 голосов
/ 21 января 2019

Похоже, ваш вариант использования требует почти (если не) полного сканирования графика. Это очень распространенный вариант использования графиков, и вы можете увидеть некоторые его случаи здесь . С степенью централизации является одним из наиболее популярных вариантов использования.

Если вы добавите логику агрегации на прикладной уровень, то упустите самое большое преимущество библиотеки графов Tinkerpop. Проходы OLAP очень быстрые.

Обратите внимание:

Что на практике, если вы используете обход компьютера / olap графа, вы должны делать это в среде, где график относительно статичен. Это связано с тем, что OLAP traversals в tinkerpop сериализует график в структуру памяти. Таким образом, изменения в графике должны быть повторно сериализованы. В быстро меняющихся условиях это может существенно замедлить ход событий.

Надеюсь, это поможет.

...