yan*_*uli 6 graph social-networking neo4j graph-databases data-structures
我需要维护一个大的有向图G,可能有数百万个节点和边.可能它可能不适合记忆.
我需要在此图表上执行的一些常见操作包括:
每个节点/边将具有与之关联的用户定义属性,例如访问计数,权重等.
对于每个节点(顶点),我将需要根据属性值执行有效的查询.例如,找到X值大于v1但小于v2的节点.这可能需要在某些字段上构建索引.
我需要找到给定节点的所有传入边和传出边,并更新边的权重.
我将需要从给定节点进行本地(基于DFS)遍历,并返回满足某个用户定义谓词的所有路径(此谓词可以使用路径中节点/边的属性值).
我需要有效地添加/删除节点/边缘.但是,这并不像操作1,2,3那样频繁地执行.
图中可能存在一些比其他部分更频繁访问的热点,我想将这些热点缓存在内存中.
以最少的实施努力实现这一目标的有效方法是什么？
我正在看一些基于磁盘的图形数据库,例如Neo4j/InfiniteGraph/DEX.尽管它们支持上述所有操作,但由于我不需要它们提供的许多功能,例如一致性/并发控制或基于群集的复制,因此它似乎是一种矫枉过正.此外,它们中的很多都基于Java,我更喜欢使用C/C++接口.
基本上我只需要一个磁盘上的图形库,它可以有效地处理持久性,节点查询和本地遍历.您对我可以使用的现有(开源)项目有什么建议吗？如果没有,实施这样的事情的最佳方式是什么？
我见过一些包含数百万个节点的大型图。我建议你找到一个点，你应该做一个加权压缩。因此，您将采用 N 个节点，使用平均值和权重压缩为 N/M 个节点......然后重建图形。
您可以在您选择的每一个节点之后重新压缩。原因是，随着一切变得巨大，从某种意义上说，随着时间的推移，你将能够使其正常化。
你有一个有向图。当你在大节点上传递更大的值时，你可以说，如果 A>B>(E&D)>H，那么你可以说：A>H。
它确实允许您根据节点之间的最短跳转来确定节点之间的公共路线。如果它不在压缩列表中，它至少会前往某个区域，并且可以根据...在某种意义上进行解压缩。