利用局部性的图形数据库

Question

DAG =有向无圈图；根=无传入边的顶点。

我有一个比可用RAM更大的DAG，所以我需要一个基于磁盘的图形数据库来处理它。

我的DAG很浅:我有数十亿根节点，但是每个节点只有几十个节点可以访问。

它也没有很好地连接:大多数节点只有一个传入的边缘。因此，对于任意一对根节点，可达子图通常很少有共同的节点。

因此，我的DAG可以被认为是大量的小树，其中只有很少的相交。

我需要在我的DAG上以批量编号执行以下查询:给定一个根节点，可以从它访问所有节点。

它可以被看作是一个批处理查询:给定几千个根节点，返回从那里可以到达的所有节点。

据我所知，有一些算法可以提高图表的磁盘存储局部性。三个例子是：

• pacher.pdf
• http://www.cs.ox.ac.uk/dan.olteanu/papers/g-store.pdf
• http://graphlab.org/files/osdi2012-kyrola-blelloch-guestrin.pdf

似乎还有一些老一代的图形数据库不使用图的局部性。例如，一个流行的Neo4j图形数据库：

http://www.ibm.com/developerworks/library/os-giraph/

Neo4j依赖于图的数据访问方法，而不考虑数据局部性，而图的处理主要涉及随机数据访问。对于无法存储在内存中的大型图形，随机磁盘访问成为性能瓶颈。

我的问题是:是否有适合我的工作负载的图形数据库？

对Win64的支持，以及从Java以外的其他地方使用数据库的可能性是一个优势。

Answer 1

从任务本身看，似乎不需要图形数据库。您可以简单地使用一些外部内存编程库，例如stxxl。首先对图执行拓扑排序(以边缘格式)。然后，您只按顺序扫描，直到完成所有“根节点”。I/O复杂度受拓扑排序的限制。实际上，您不需要一个topo排序，只需要标识根节点。这可以通过连接边缘表和节点表来完成，这是线性时间。