如何将图划分为可能重叠的部分,使得任何顶点都包含在距离边界至少有k距离的部分中?
问题出现在不能将整个图加载到单个机器的情况下因为没有足够的内存。另一个要求是分割一个相等数目的顶点。
是否存在最小化部分之间公共顶点的算法?
这里的用例是这样的:你想从一个初始顶点开始执行查询,你知道这个顶点需要最大k次遍历。如果部件包含此查询的所有顶点,则结果为零网络利用率。因此,问题是如何减少这样一个分区的内存开销。
有我应该读的书吗?
我发现这个看起来很有希望:http://grafia.cs.ucsb.edu/sedge/docs/sedge-sigmod12-slides.pdf
这不是巧合,谷歌决定使用哈希分区。找到一个好的分区是很困难的。我也将使用散列分区,希望如此说明数据中心有良好的网络带宽您可以使用广度优先搜索来获得与所讨论的节点只有k距离的所有节点,从节点本身开始。当到达距离原点k处时,可以结束搜索。
编辑:使用深度优先搜索来分配从边界属性到每个节点的最小距离。一旦完成了深度优先搜索,通过节点的简单迭代就可以提供分区。例如,您可以创建一个表,将到边界的最小距离存储为键,并将节点向量存储为表示分区的值。