Эффективный способ внедрения LinkedIn, например, Как вы связаны с функцией?

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

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

Хотя это звучит аккуратно, проблема в том, что для определения друзей каждого человека необходим отдельный запрос к БД. Когда сеть идет глубже двух уровней, это может потребовать много времени. Есть ли более эффективная альтернатива? Если нет, как мы можем добавить лучшую аппаратную поддержку (параллельные вычисления, гриды, распределенную базу данных и т. Д.), Чтобы сократить время, необходимое для вычислений?


database performance graph social-networking hardware
person Chirantan    schedule 13.10.2009    source источник
comment
Мне пришлось удалить изображение из вашего сообщения, потому что ImageShack удалил его и заменил рекламным. См. meta.stackexchange.com/q/263771/215468 для получения дополнительной информации. Если возможно, было бы здорово повторно загрузить их. Спасибо!   -  person Undo    schedule 28.09.2015

Ответы (2)


arrow_upward
5
arrow_downward

Вы можете увидеть, как это сделать, в статье Графики в базе данных: SQL встречается с социальными сетями Лоренцо Альбертона. Код примера написан для PostgreSQL с использованием CTE. Однако я сомневаюсь, что использование СУБД для этого будет хорошо. Я написал статью о том, как сделать то же самое, что и в упомянутой статье, используя собственную базу данных графов, в данном случае Neo4j: Социальные сети в базе данных: использование база данных графов. Помимо различий в производительности, база данных графов также упрощает задачу, предоставляя API-интерфейс графа, который упрощает обработку обходов, которые было бы чрезвычайно сложно написать на SQL (или с помощью хранимых процедур). Я написал немного больше о базах данных графов в этой ветке и см. и этот тоже.

person nawroth    schedule 13.10.2009

arrow_upward
1
arrow_downward

Без какой-либо рекурсивной хранимой процедуры (CTE в SQL Server 2005+) вам понадобится несколько циклов приема-передачи по мере того, как уровни становятся глубже. Однако хорошая инфраструктура кеширования действительно может повысить производительность, поскольку списки подключений наиболее популярных / активных пользователей останутся кэшированными. Механизм чтения / записи через кеш сделает ситуацию еще лучше (обновления кеша переходят в обновления БД, чтение из кеша происходит каскадно в чтение БД)

person Chris    schedule 13.10.2009
comment
это хороший комментарий, потому что многие люди не хотят просто полагаться на SQL Server CTE, Procs или другой T-SQL, чтобы всегда выполнять рутинную работу. Сохраните его в SQL Server, а затем, как вы заявили, кешируйте один раз, например, в своем приложении C #, и используйте его в памяти для поиска, если это только для небольшого набора данных. - person PositiveGuy; 25.03.2013