database - 利用局部性的图形数据库

Question

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

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

我的 DAG 很浅:我有数十亿个根节点，但从每个节点只能到达几十个节点。

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

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

我需要在我的 DAG 上批量执行以下查询:给定一个根节点，获取从它可到达的所有节点。

它可以被认为是一个批量查询:给定几千个根节点，返回从那里可达的所有节点。

据我所知，有一些算法可以改进图形的磁盘存储位置。三个例子是:

• http://ceur-ws.org/Vol-733/paper_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 relies on data access methods for graphs without considering data locality, and the processing of graphs entails mostly random data access. For large graphs that cannot be stored in memory, random disk access becomes a performance bottleneck.

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

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

Answer 1

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