node.js - 如果我在图形 Node 中有 2way 关系并且 Node 相互关联，则 Neo4j 查询最短路径卡住(不工作)

Question

我将关系图设为两种关系，比如如果 A 知道 B 那么 B 就知道 A，每个 Node 都有唯一的 ID 和名称以及其他属性。所以我的图看起来像

如果我触发一个简单的查询MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}),path = (p1)-[:NAVIGATE_TO*]-(p2) 返回路径 它没有给出任何响应，并消耗了机器 100% 的 CPU 和 RAM。

---

已更新当我阅读帖子和这篇帖子的评论时，我简​​化了模型和关系。现在它结束了

每个关系都有不同的权重，为了简化考虑水平连接权重 1，垂直权重 1 和对角线关系具有权重 1.5在我的数据库中有超过 85000 个 Node 和 30 万个关系

使用最短路径的查询不会以某种结果结束。它卡在处理中，CPU 达到 100%

Answer 1

恐怕你在这里做不了什么。您的图表非常具体，仅与最近的 Node 有关系。那太糟糕了，因为 neo4j 可以围绕起点玩 +- 很少的关系，而不是每个查询的整个图

这意味着，一旦您离开 2 个 Node ，计算复杂度将增加到:

8 relationships per node
distance 2
8 + 8^2

一般来说，距离n的最高复杂度是

O(8 + 8^n) //in case all affected nodes have 8 connections

你说，你有 ~80 000 个 Node 。这意味着(如果我错了请纠正我)，~280 的最长距离(来自 √80000).让我们假设你的 Node

(p1:SearchableNode {name: "Ishaan"}), 
(p2:SearchableNode {name: "Garima"}),

只有 140 个希望。这将产生 8^140 = 10e126 的复杂性，我不确定世界上是否有任何计算机可以处理这个问题。

当然，并非所有 Node 都有 8 个连接，只有那些“在中间”的 Node ，在我们的示例图中，它将有大约 500 000 个关系。你得到了大约 300 000，这可能少了 2 倍所以让我们假设平均距离为 70(满分 140 - 一个非常宽松的底部估计)的总体复杂性对于平均具有 4 个关系的 Node (从 8、80 000 下降) *4 = 320 000) 是

O(4 + 4^70) = ~10e42

一个 1GHz CPU 应该能够通过以下方式计算:

-1000 000 per second
10e42 == 10e36 * 1 000 000 -> 10e36 seconds

假设我们有一个 100 个 10Ghz cpu 服务的集群，总共 1000 GHz。那仍然是 10e33 * 1 000 000 000 -> 10e33seconds

我建议远离 AllshortestPaths，只查找第一条可用路径。使用 gremlin 而不是 cypher 可以通过一些启发式方法实现自己的算法，因此实际上您可以将时间缩短到几秒或更短。

示例:仅使用一个方向 = 减少到 10e16 秒。

示例启发式:检查 Node 的id，node2.id - node1.id 之间的差异(减法值)越大，实际距离越大(考虑 Node 创建顺序 - 具有相似id的 Node 接近一起)。在这种情况下，您可以跳过查询或使用 MATCH n1-[:RELATED..5]->q-[:RELATED..*]->n2 之类的东西跳过一些关系(我忘记了语法定义精确关系计数) 这将(应该)实际跳转(立即跳到)5 距离远的 Node ，这些 Node 更接近 n2 Node = 复杂性从 4^70 降低 到 4^65。因此，如果您可以准确计算与 Node id 的距离，您甚至可以匹配 ... [:RELATED..65] ... 这会将复杂性降低到 4^5 这对于 cpu 来说只是几毫秒的问题。

我这里可能完全错了。我已经离开学校一段时间了，很高兴请一位数学家(图论)来证实这一点。