database - 在图数据库中找到某种类型的 N 个邻居

Question

假设我有一个包含 100k 个节点和 500k 个边的有向图。其中有 15k 个节点是“重要的”。我需要从一个特定节点开始找到 100 个最近的“重要”节点。

我已经在 C# 中实现了 Dijkstra 算法，它可以找到从起始节点到所有其他节点的距离。然后我按距离对“重要”节点进行排序并首先返回 100。这大约需要 1 秒钟。

现在我需要在服务器端 (Linux) 执行相同的操作，可能有很多并发查询和不同的起始节点。我已经尝试过 node4j 图形数据库，在与开发人员协商后，我们得到了在 10-20 秒内完成相同操作的解决方案(实际上，如果我们计算没有长度限制的路径，大约需要 10 分钟)。需要这么长时间，因为 neo4j 存储所有最短路径，而我的 C# 实现只存储距离。在 neo4j 中使其更快的唯一选择是编写重要的扩展。

所以问题是:是否有可以在 Linux 服务器上安装并能够快速运行此类查询的图数据库(非商业版)？我检查了维基百科列表中的所有图形数据库，但没有找到合适的。

另一种选择是在 Java 中实现相同的算法并创建一个服务(Tomcat？)来存储图形的共享副本(如何？)并回答这些查询。但我更喜欢现成的东西......

Answer 1

编写 Neo4j 扩展来执行此操作并不像您想象的那么糟糕。

看这里的例子: http://maxdemarzi.com/2012/11/26/extending-neo4j/

这个使用 A* 算法进行“自定义”寻路: http://maxdemarzi.com/2012/11/27/pathfinding-with-neo4j-unmanaged-extensions/