Мне кажется, что проблема действительно сводится к тому, как мы хэш/трек 1 миллиард пользователей, поскольку мы рассчитываем друзей на каждом уровне. (Обратите внимание, что нам нужно только их подсчитать, НЕ хранить их)
Если мы предположим, что для каждого человека их друг и друзья их друзей имеют очень маленький порядок (скажем < 1000 и < 100 000), это кажется практичным хранить их в таблицах базы данных для каждого пользователя. Для этого требуется только два управляемых прохода всей базы данных, а затем прямые добавления к таблицам при создании «новых» отношений.
Если у нас есть 1-й и 2-й друг степени, хранящегося в таблицах пользователей, мы можем использовать эти продлить насколько нам нужно -
EG: к COUNT 3-го друга степени мы должны хэширования и отслеживать 1-й степени друзей всех друзей второй степени. (для 4-й степени вы делаете все 2-ые Секунды, для более высоких степеней вы создаете 4-й, а затем соответствующим образом расширяетесь до 5-го или 6-го).
Итак, в этот момент (друзья 5-й и 6-й степени) вы начинаете приближаться к 1 миллиарду людей, как количество людей, которые вам нужно отслеживать, хешировать и считать.
Я думаю, что тогда возникает проблема, что является самым эффективным способом иметь 1 миллиард идентификаторов записи, поскольку вы «считаете» друзей в отношениях более высокого порядка.
Как вы это делаете, я не знаю - какие-то мысли?
использование ширина первый поиск. BFS гарантирует, что всех друзей степени 1 ищут до степени 2, и всех друзей степени 2 ищут до степени 3 и т. Д. Когда вы посещаете каждого неоткрытого друга, отметьте его как обнаруженное и увеличите счет на единицу. Имейте переменную для отслеживания степени поиска. Остановитесь, когда всех друзей 5-й степени посетили. –
@ JasonL- В большой социальной сети это исследует такое огромное количество узлов, что это будет чрезмерно дорого. – templatetypedef
Может ли это быть сделано разумно с помощью одного изначально дорогого полнографического поиска (возможно, используя материал матрицы вместо BFS), а затем, когда соединения или пользователи добавляются или удаляются, вы идете «мои друзья k-й степени - это союз над всеми (k-1) -ой степени друзья моих друзей первой степени "? Если вы хотите, чтобы люди были перечислены для наименьшего k, который относится к ним, это, очевидно, означает некоторую очистку после этой заданной операции. –