Комментарии 2
спасибо за статью! однако хотелось бы уточнить пару моментов
1) что имеется ввиду под "можно посылать только второй путь" во втором способе?
предположим, у нас 3 пользователя хранятся на 3 партициях и все они знакомы между собой, тогда по постановке задачи данные выглядят вот так
[part1] A->B,C
[part2] B->A,C
[part3] C->A,B
мы составляем все возможные пути длины 2 и собираем - в этом примере пути будут ABC, BAC, CAB, пусть сами пути мы не трогаем, но группируем все по А, получаем 1 эго-граф для
[part1] А -> [(BC), (BC), (CB)] - правильно?
Тогда прост не очень понятно, где что не посылаем. И не совсем понятно, что насчет эго-графов для B и С - ведь для их тоже нужно построить?
2) С фильтром Блума тоже не совсем очевидно - мы готовим фильтр Блума, просматривая друзей Гари - это означает, что устанавливается какой-то порядок составления эго-графов? Т.е. весь процесс становится не параллельным?
Еще я так понимаю сам фильтр никуда не передается, а только служит для фильтрации того, какие пути длины 2 составлять?
1) кажется, частично разобрался:
если id пользователей соответствуют алфавитному порядку, то первым в каждой тройке мы располагаем человека с минимальным id, потом "овнера" списка друзей и потом кого-то еще. Тогда для самого Боба не будет ни одной тройки, в которой он бы шел первым - поэтому его списка друзей и нет на второй картинке - таким образом, граф Боба составлен из пар, сгенерированных на списках его друзей. Составление графа - уже дело техники - просто зная корень, составляем его на основании всех пар, попавших в группу.
В моем примере мы составим пути
[p1] BAC, [p2]ABC, [p3] ACB
и группируя по A получим пары ребер [B,C] [C,B] - что собственно и дает треугольник для A
как можно сгенерировать графы для C и B - можно конечно генерировать вообще все возможные пути, типа
[p1]BAC,CAB [p2]ABC,CBA [p3]ACB,BCA
тогда это решит задачу, но в таком случае будет существенно больше троек и шаффл хоть и будет один, количество троек растет как N*(N-1) - растет кол-во данных для шаффла
Ускоряем распределенную обработку больших графов с помощью вероятностных структур данных и не только