6

我需要维护一个大的有向图 G，可能有数百万个节点和边。它可能不适合内存。

我需要在此图上执行的一些频繁操作包括：

  1. 每个节点/边都将具有与其关联的用户定义属性，例如访问计数、权重等。

  2. 对于每个节点（顶点），我需要根据属性值执行有效的查询。例如，找到 X 值大于 v1 但小于 v2 的节点。这可能需要在某些字段上建立索引。

  3. 我需要找到给定节点的所有传入边和传出边，并更新边的权重。

  4. 我需要从给定节点进行本地（基于 DFS）遍历，并返回满足某个用户定义谓词的所有路径（该谓词可能使用路径中节点/边的属性值）。

  5. 我需要有效地添加/删除节点/边。但是，这不像操作 1、2、3 那样频繁地执行。

图中可能有一些热点比其他部分更频繁地被访问，我想将这些热点缓存在内存中。

以最少的实施工作来实现这一目标的有效方法是什么？

我正在研究一些基于磁盘的图形数据库，例如 Neo4j/InfiniteGraph/DEX。尽管它们支持上述所有操作，但这似乎有点过头了，因为我不需要它们提供的很多功能，例如一致性/并发控制或基于集群的复制。此外，其中很多都是基于 Java 的，我更喜欢带有 C/C++ 接口的东西。

基本上我只需要一个磁盘上的图形库，它可以有效地处理持久性、节点查询和本地遍历。您对我可以使用的现有（开源）项目有什么建议吗？如果没有，实现这样的事情的最佳方法是什么？

4

1 回答 1

1

我见过一些包含数百万个节点的大图。我建议你找到一个点，你应该做一个加权压缩。因此，您将采用 N 个节点，使用平均值和权重压缩成 N/M 个节点......然后重建图形。

您将根据自己的选择在每隔这么多节点之后重新压缩。原因是随着一切变得巨大，你将能够，在某种意义上，随着时间的推移使其正常化。

你有一个有向图。当你在大节点上传递更大的数据时，你可以说，如果 A>B>(E&D)>H，那么你可以说：A>H。

它确实允许您根据节点之间的最短跳转来确定节点之间的公共路线。如果它不在压缩列表中，它至少会朝着某个区域前进，并且可以根据...在某种意义上解压缩。

于 2013-06-19T18:05:12.237 回答