有效的实现LinkedIn的方式，例如“如何连接到”特征？ [英] Efficient way to implement LinkedIn like "How you are connected to" feature?

问题描述

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

LinkedIn has this cool feature in which while visiting some user's profile, LinkedIn prompts how you are connecting to that user through the network.

假设访问者和个人资料所有者是图的两个节点，其中节点代表用户，而边表示友谊，一个简单的解决方案可以是从节点达到一定水平，并查看是否有任何交叉。交叉点将是网络链路节点。

Assuming that the visitor and the profile owner are two nodes of a graph where the nodes represent users and edge represents friendship, a simple solution could be a bfs starting from both the nodes up to certain level and see if there are any intersections. The intersections would be the network link-nodes.

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

Although this sounds neat, the problem is that in order to determine friends of each person, a separate DB query is needed. When the network goes deeper than 2 levels, it would be highly time consuming algorithm. Is there a better efficient alternative? If not, how can we add better hardware support (parallel computing, grids, distributed database etc) in order to bring down the time required for computation?

推荐答案

您可以在文章数据库中的图表：SQL遇到社交网络 Lorenzo Alberton。示例代码是使用CTE为PostgreSQL编写的。但是，我怀疑使用 RDBMS 可以获得良好的效果。我写了一篇文章，关于如何做同样的东西，如上述文章中使用本机图数据库，在这种情况下 Neo4j ：数据库中的社交网络：using图形数据库。除了性能上的差异，图形数据库还通过提供一个图形API来简化任务，这使得易于处理在SQL中写入（或通过使用存储过程）非常复杂的遍历。我在此主题中对图表数据库进行了更多的写作，并查看了这一个。

You can see how this can be done in the article Graphs in the database: SQL meets social networks by Lorenzo Alberton. The example code is written for PostgreSQL using CTEs. However, I doubt that using a RDBMS for this will perform well. I wrote up an article on how to do the same stuff as in the mentioned article using a native graph database, in this case Neo4j: Social networks in the database: using a graph database. Other than the differences in performance, a graph database also simplifies the task by providing a graph API that makes it easy to handle traversals that would be extremely complex to write in SQL (or by using stored procedures). I wrote a bit more on graph databases in this thread and see this one too.

这篇关于有效的实现LinkedIn的方式，例如“如何连接到”特征？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！