f*********m
发帖数: 726 | 1 Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)
不会涉及到graph merge/split 的问题吧？
能不能把每个边界node都存两个copy，两个相邻的机器各一个？比如：node_a和node_b
是边界node，在两台机器上各有一个copy。
机器1 机器2
node_c---node_a---node_b | node_a---node_b---node_d
|
找node_a的k-level 邻居，可以先在机器1上用bfs,遇到node_b后（可以给node_b一个
标签，说明他在机器2上也有copy），可以继续在机器2上bfs。
不过题目给定只要3-level邻居，会不会有什么更有效的方法？ | s*****V
发帖数: 21731 | 2 2不太简单了，每个机器找直系朋友，然后看看有没有交集。 | f*********m
发帖数: 726 | 3 问题是对于存在一台机器上的graph的边界节点，他的直系朋友可能存储在另一他机器
上，也就是是说，他通往直系朋友的edge被cut了。怎么处理这种情况？
【在 s*****V 的大作中提到】
: 2不太简单了，每个机器找直系朋友，然后看看有没有交集。
| b********h
发帖数: 119 | 4 BFS using MapReduce
communication)
_b
【在 f*********m 的大作中提到】
: Given a social graph, find if there is a path between two persons with at
: most 2 steps (3rd level connection), how to handle it in distributed way (
: large graph stored at a large number of nodes, minimize cross-communication)
: 不会涉及到graph merge/split 的问题吧？
: 能不能把每个边界node都存两个copy，两个相邻的机器各一个？比如：node_a和node_b
: 是边界node，在两台机器上各有一个copy。
: 机器1 机器2
: node_c---node_a---node_b | node_a---node_b---node_d
: |
: 找node_a的k-level 邻居，可以先在机器1上用bfs,遇到node_b后（可以给node_b一个
| f*********m
发帖数: 726 | 5 能否说详细些。谢谢。
【在 b********h 的大作中提到】
: BFS using MapReduce
:
: communication)
: _b
| c****e
发帖数: 1453 | 6 Mapreduce is not efficient for graph algorithms.
You can simply partition the adjacency list on nodeId. Since each node knows
its neighbors, the start node (A) and end node(B) can exchange their AJL to
minimize the communication to other machines. | b*****e
发帖数: 474 | 7 Using brutal force:
is2stepsConnected(A, B) : bool
foreach node n, SA(n) = set of person linked from A
SB(n) = set of person linked to B
UA = Union SA(n)
UB = Union SB(n)
foreach node n, isConnected(n) = exists edge E (X, Y)
such that X in UA and Y in UB
return OR isConnected(n)
Same thing using equivalent database query: table Graph contains edges (X, Y
):
SELECT X, Y from Graph G
WHERE G.X in (SELECT K.Y from Graph K WHERE K.X = A)
AND G.Y in (SELECT P.X from Graph P WHERE P.Y = B)
communication)
_b
【在 f*********m 的大作中提到】
: Given a social graph, find if there is a path between two persons with at
: most 2 steps (3rd level connection), how to handle it in distributed way (
: large graph stored at a large number of nodes, minimize cross-communication)
: 不会涉及到graph merge/split 的问题吧？
: 能不能把每个边界node都存两个copy，两个相邻的机器各一个？比如：node_a和node_b
: 是边界node，在两台机器上各有一个copy。
: 机器1 机器2
: node_c---node_a---node_b | node_a---node_b---node_d
: |
: 找node_a的k-level 邻居，可以先在机器1上用bfs,遇到node_b后（可以给node_b一个
|
|
