x*****n
发帖数: 195 | 1 板上看到的，看下面的讨论没有很好的解答。。。求大牛指点。
对于linkedin上任意两个用户，精确判断他们上1st connection（直接互为好友），还
是2nd，3rd（隔来一个朋友，两个朋友），等等。如果是直接好友，显示他们的共同好
友；否则显示他们怎样通过各自的朋友连起来（通过朋友1再通过朋友2）。请设计数据
结构和算法。怎样把数据存储map到多台机器上。
我自己使用linkedin的经验一般也就显示到最多3rd，觉得还是kv store的思路，可以
在机器上按user id范围分布存储该用户的好友关系信息到不同机器上，运行时直接计
算两个user有没有直连，或者有共同好友，或者共同好友有共同好友。不知道怎样是不
是推荐的做法？
看到有个概念叫graph db，存储关系信息的，不知道这里是不是用得上。 |
e***i
发帖数: 231 | 2 results from google search give some hints "linkedin social graph
architecture"
Might be helpful
https://engineering.linkedin.com/real-time-distributed-graph/using-set-cover
-algorithm-optimize-query-latency-large-scale-distributed
http://blog.karmona.com/index.php/2008/12/30/the-social-graph-c
http://hurvitz.org/blog/2008/06/linkedin-architecture
【在 x*****n 的大作中提到】
: 板上看到的，看下面的讨论没有很好的解答。。。求大牛指点。
: 对于linkedin上任意两个用户，精确判断他们上1st connection（直接互为好友），还
: 是2nd，3rd（隔来一个朋友，两个朋友），等等。如果是直接好友，显示他们的共同好
: 友；否则显示他们怎样通过各自的朋友连起来（通过朋友1再通过朋友2）。请设计数据
: 结构和算法。怎样把数据存储map到多台机器上。
: 我自己使用linkedin的经验一般也就显示到最多3rd，觉得还是kv store的思路，可以
: 在机器上按user id范围分布存储该用户的好友关系信息到不同机器上，运行时直接计
: 算两个user有没有直连，或者有共同好友，或者共同好友有共同好友。不知道怎样是不
: 是推荐的做法？
: 看到有个概念叫graph db，存储关系信息的，不知道这里是不是用得上。
|
l*3
发帖数: 2279 | 3 我是小白，不懂什么大规模数据。只想弱弱的问一句，难道现在所谓的码农连图的广度
优先搜索都不知道了吗？。。。。 |
n******n
发帖数: 12088 | 4 说的就是大数据。
【在 l*3 的大作中提到】
: 我是小白，不懂什么大规模数据。只想弱弱的问一句，难道现在所谓的码农连图的广度
: 优先搜索都不知道了吗？。。。。
|
w*****t
发帖数: 190 | 5 这个至少不是普通的BFS吧。题目讲了是map到多台机器的
【在 l*3 的大作中提到】
: 我是小白，不懂什么大规模数据。只想弱弱的问一句，难道现在所谓的码农连图的广度
: 优先搜索都不知道了吗？。。。。
|
g*********e
发帖数: 14401 | 6 linkedin's current graph db can only find connections when the intermediate
hop is <= 3 |
x*****n
发帖数: 195 | 7 这样的话每个user的record存他的所有好友列表就行了。然后实时计算任意uer间的关
系，一般人有个2、3千connection也到头了吧，时间复杂度感觉还能忍。真不行就把
2nd的离线计算好。离线计算所有3rd connection存储上应该太浪费了。
哪位有实际开发经验的大牛讲讲？
intermediate
【在 g*********e 的大作中提到】
: linkedin's current graph db can only find connections when the intermediate
: hop is <= 3
|
c*****n
发帖数: 35 | 8 neo4j
板上看到的，看下面的讨论没有很好的解答。。。求大牛指点。对于linkedin上任意两
个用户，精确判断他们上1st connection（直接互为好友），还是2nd，3rd（隔来....
....
【在 x*****n 的大作中提到】
: 板上看到的，看下面的讨论没有很好的解答。。。求大牛指点。
: 对于linkedin上任意两个用户，精确判断他们上1st connection（直接互为好友），还
: 是2nd，3rd（隔来一个朋友，两个朋友），等等。如果是直接好友，显示他们的共同好
: 友；否则显示他们怎样通过各自的朋友连起来（通过朋友1再通过朋友2）。请设计数据
: 结构和算法。怎样把数据存储map到多台机器上。
: 我自己使用linkedin的经验一般也就显示到最多3rd，觉得还是kv store的思路，可以
: 在机器上按user id范围分布存储该用户的好友关系信息到不同机器上，运行时直接计
: 算两个user有没有直连，或者有共同好友，或者共同好友有共同好友。不知道怎样是不
: 是推荐的做法？
: 看到有个概念叫graph db，存储关系信息的，不知道这里是不是用得上。
|
k***5
发帖数: 583 | 9 这想的太简单了，如果把约束条件变成系统有50K用户，要对50K用户进行map，一个图
的广度优先搜索做50K次，会跑死系统的。
【在 l*3 的大作中提到】
: 我是小白，不懂什么大规模数据。只想弱弱的问一句，难道现在所谓的码农连图的广度
: 优先搜索都不知道了吗？。。。。
|
b*****p
发帖数: 9649 | |
x****u
发帖数: 12955 | 11
4th level connection is already too remote to be any benefit anyway. By 7th
level, you could be connected to virtually everybody on the internet.
【在 x*****n 的大作中提到】
: 这样的话每个user的record存他的所有好友列表就行了。然后实时计算任意uer间的关
: 系，一般人有个2、3千connection也到头了吧，时间复杂度感觉还能忍。真不行就把
: 2nd的离线计算好。离线计算所有3rd connection存储上应该太浪费了。
: 哪位有实际开发经验的大牛讲讲？
:
: intermediate
|
k******a
发帖数: 44 | 12 直接用BFS会计算量太大，
如果每个用户是100个朋友，那么从A到B，如果B是A得二级朋友，那么要扫描100*100各
节点。
如果从A扫，再从B扫，再查看交集，那么就是100+100个节点。 |
