9

LinkedIn 有一个很酷的功能,在访问某些用户的个人资料时,LinkedIn 会提示您如何通过网络连接到该用户。

假设访问者和个人资料所有者是图中的两个节点,其中节点代表用户,边代表友谊,一个简单的解决方案可以是从两个节点开始到某个级别的 bfs,看看是否有任何交叉点。交叉点将是网络链接节点。

虽然这听起来很简洁,但问题是为了确定每个人的朋友,需要单独的数据库查询。当网络深度超过 2 层时,这将是一个非常耗时的算法。有没有更有效的替代方案?如果没有,我们如何添加更好的硬件支持(并行计算、网格、分布式数据库等)以减少计算所需的时间?

4

2 回答 2

5

您可以在Lorenzo Alberton的文章Graphs in the database: SQL meet social networks中了解如何做到这一点。示例代码是使用 CTE 为 PostgreSQL 编写的。但是,我怀疑为此使用RDBMS会表现良好。我写了一篇关于如何使用本机图形数据库做与上述文章相同的事情的文章,在本例中是Neo4j数据库中的社交网络:使用图形数据库。除了性能上的差异之外,图形数据库还通过提供图形 API 来简化任务,该 API 可以轻松处理用 SQL 编写(或使用存储过程)极其复杂的遍历。我在这个线程中写了更多关于图形数据库的内容,看看这个也是。

于 2009-10-13T07:33:24.333 回答
1

如果没有某种递归存储过程(SQL Server 2005+ 中的 CTE),随着级别的深入,您将需要多次往返。然而,一个好的缓存基础设施确实可以提高性能,因为最受欢迎/活跃用户的连接列表将保持缓存。通过缓存机制的读/写会使事情变得更好(缓存更新级联到数据库更新,缓存读取级联到数据库读取)

于 2009-10-13T05:18:48.363 回答