在磁盘上存储非常大的图形/流图分区算法？

Question

在磁盘上存储非常大的图形/流图分区算法？

13

假设我有一个非常大的无向、无权图（从数亿个顶点开始，每个顶点约有10条边），非分布式且仅由单个线程处理，并且我想在它上面进行广度优先搜索。我预计它们会受到I/O限制，因此我需要一个适用于BFS的磁盘页面布局，磁盘空间不是问题。搜索可以从每个顶点以相等的概率开始。直观地说，这意味着最小化不同磁盘页面上顶点之间的边数，这是一个图分区问题。

图本身看起来像一条意大利面条，想象一组随机连接的点，其中一些倾向于更短的边。

问题是，如何对这么大的图进行分区？我找到的可用图分区器只能处理适合内存的图。我找不到任何流图分区算法的描述或实现。

或者，也许有一种替代方法可以获得适用于BFS的磁盘布局？

现在作为近似值，我使用顶点附加的空间坐标，并按照希尔伯特排序顺序将顶点放在磁盘上。这样，空间接近的顶点会落在同一页上，但它们之间的边的存在或不存在完全被忽略了。我能做得更好吗？

另一种选择是，我可以使用希尔伯特排序顺序将图分成几个部分，对子图进行分区，然后将它们拼接在一起，并接受接缝处的较差分区。

我已经研究过一些东西：

如何存储数十亿个节点和顶点的大型有向无权图
http://neo4j.org/ - 我没有找到它如何在磁盘上进行图形布局的任何信息

分区实现（除非我弄错了，否则所有实现都需要将图形适合内存）：

编辑：关于图形外观和 BFS 能够从任何位置开始的信息。编辑：有关对子图进行分区的想法。

- Laurynas Biveinis

2个回答

2

您可能想要查看HDF5。尽管H代表分层，但它可以存储图形，请在关键字“组”下查看文档，并且它专为非常大的数据集而设计。如果我理解正确，HDF5“文件”可以分布在多个操作系统“文件”中。现在，HDF5只是一个数据结构，再加上一组用于低级和高级操作数据结构的库。我没有头绪关于流图分区算法，但我坚持认为，如果您正确地处理数据结构，则算法变得更容易实现。

您已经知道有关mega-graph的什么信息？它自然地分成密集的子图，这些子图本身稀疏连接吗？对于磁盘存储，拓扑排序是否比现有的空间排序更好？

如果无法给出明确的答案，也许您只需多次读取图形以构建分区，在这种情况下，您只需要尽可能快的I/O，对节点上的分区进行复杂的布局很好，但不是那么重要。如果您可以将图形分区为子图，这些子图本身与其他子图只有单个边缘相连，则可以使问题更易处理。

你想要一个适合 BFS 的布局，但是 BFS 通常应用于树。你的图中有唯一的根节点可以从中开始所有 BFS 吗？如果没有，那么从一个顶点开始的 BFS 的布局对于从另一个顶点开始的 BFS 将是次优的。

- High Performance Mark

谢谢您的建议。我之前遇到过HDF5，但没有想到可以用它来存储图形。我会研究一下。这个图形并不自然地分割，可以想象成意大利面条。关于拓扑排序 - 对于无向图，任何顶点的排序都是有效的拓扑排序吗？关于BFS - 它可以从任何顶点开始。另外，我突然想到可以将希尔伯特排序的图形分成内存大小的块，对这些块进行分区，并在块之间接受次优的分区。 - Laurynas Biveinis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rex Kerr · Accepted Answer

没有算法真正需要“适应内存” - 您始终可以根据需要分页。但是，您希望避免计算时间过长 - 在通用情况下进行全局图分区是NP完全问题，对于大多数甚至不适合内存的问题来说，这是“不合理的长”。

幸运的是，您想要进行广度优先搜索，这意味着您需要一种广度优先计算很容易的格式。我不知道有任何算法可以做到这一点，但是如果您愿意允许一些额外的磁盘空间，可以构建自己的广度优先布局。

如果边缘没有偏向于本地交互，则解开图形将很困难。如果它们偏向于本地交互，则建议使用以下算法：

1. 从整个数据集中选择一组随机顶点作为起始点。 2. 对于每个顶点，请收集所有相邻的顶点（需要扫描一遍数据集）。 3. 对于每组相邻的顶点，请收集其相邻顶点集，并根据连接到它们的边数进行排名。如果您没有页面中存储所有顶点的空间，请保留最有连接的顶点。如果您有空间保存它们全部，则可能希望丢弃最不有用的顶点（例如，如果页面内保留的边的分数/需要存储的顶点的分数比率“太低”-其中“太低”取决于您的搜索实际上需要多少广度，以及您是否可以进行任何修剪等-则不要在邻域中包含它们）。 4. 重复收集和排名相邻项的过程，直到填满邻域（例如，填充适合您的某些页面大小）。然后检查随机选择的起点是否重复。如果有少量顶点同时出现在两个邻域中，请从其中一个删除它们，这将破坏较少的边缘。如果有许多顶点同时出现在两个邻域中，请保留具有最佳（邻域中的顶点/破坏边缘的数量）比率的邻域，并且丢弃另一个。

现在，您拥有了一些局部邻域，这些邻域在广度优先搜索中近似地处于本地最优状态。如果您的广度优先搜索可以有效地修剪无效的分支，则这可能已经足够好了。否则，您可能希望相邻的邻域聚类。

如果您不需要相邻的邻域过于聚集，则将已分组为邻域的顶点放在一边，并在其余数据上重复该过程，直到所有顶点都被计算。您将每个顶点标识符更改为（顶点，邻域），然后完成：在跟随边缘时，您知道要抓取哪个页面，给定构造方式，大多数页面都会很接近。

如果您确实需要相邻的邻域，则需要跟踪正在增长的邻域。您重复以前的过程（随机选择，增长邻域），但现在根据它们在邻域内满足的边数以及离开邻域的边的分数占现有组的比例对邻居进行排名。您可能需要加权因素，但是类似于这样的东西。

score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside)

这可能会有些效果。

现在，这并不是全局或甚至本地最优的，但这个或类似的结构应该能够提供一个良好的本地连接结构，并且应该能够让您产生一组覆盖高度互连性邻域。

同样，这取决于您的广度优先搜索是否修剪分支。如果是，廉价的方法是最大化本地互连性。如果不是，则要做的是最小化外部连接 - 在这种情况下，我建议只收集一些大小的广度优先集，并保存这些集合（在集合的边缘重复 - 您的硬盘空间受到限制吗？）。