寻求Neo4J Cypher查询很长但(几乎)独特的路径

Question

我们有一个Neo4J数据库,代表一个具有大约100K节点和200K关系的进化过程.节点是代中的个体,边缘代表父子关系.主要目标是能够在最后一代中获取一个或多个感兴趣的节点,并探索它们的进化历史(大致上,"我们是如何到达这里的？").

找到所有祖先的"显而易见的"第一个查询不起作用,因为通过该空间的祖先和路径太多了:

match (a)-[:PARENT_OF*]->(c {is_interesting: true}) 
return distinct a;

因此,我们已对数据进行了预处理,以便将某些边标记为"特殊",这样几乎每个节点最多只有一个"特殊"父边,尽管偶尔两个父边都标记为"特殊".那么,我希望这个查询能够(有效地)生成沿"特殊"边缘的(几乎)唯一路径:

match (a)-[r:PARENT_OF* {special: true}]->(c {is_interesting: true}) 
return distinct a;

然而,这仍然是非常缓慢的.

这是令人沮丧的,因为"作为一个人",逻辑很简单:从少数"有趣"节点(通常为1,从不超过几十个)开始,并沿着几乎总是独特的"特殊"边缘追逐.假设具有两个"特殊"父节点的节点数量非常少,这应该类似于O(N),其中N是时间上的代数.

在Neo4j的,但是,从这里独特的"有趣"的节点可以追溯到25步每一步都是独一无二的,但是,需要30秒,而一旦有一个单一的更快分叉(其中父母双方均为"特"),它变得更糟,因为一步骤的功能.28步(让我们到达第一个分叉处)需要2分钟,30分钟(其中只有一个分叉)需要6分钟,而我甚至没想过尝试完整的100步到模拟的开始.

去年的一些类似工作似乎表现更好,但我们使用各种边缘标签(例如,(a)-[:SPECIAL_PARENT_OF*]->(c)以及(a)-[:PARENT_OF*]->(c))而不是使用边缘上的数据字段.查询关系字段值是不是一个好主意？我们在这个模型中有一些不同的值附加到一个关系(一些布尔值,一些数字),我们希望/假设我们可以使用它们来有效地限制搜索,但也许情况并非如此.

关于如何调整我们的模型或查询的建议将不胜感激.

更新我应该提到的,这都是Neo4J 2.1.7.我将根据布莱恩·安德伍德的建议给出2.2尝试,并将报告回来.

Answer 1

在使用 Neo4J 2.2 中的分析工具进行探索之后（感谢 Brian Underwood 的提示），很明显（目前）Neo4J 不会对边缘属性进行任何预过滤，这会导致长路径下令人讨厌的组合爆炸。

例如原始查询：

match (a)-[r:PARENT_OF* {special: true}]->(c {is_interesting: true}) 
return distinct a;

找到从到 的所有路径，然后消除那些不具有边的路径。由于从到 的路径有数百万条，这是完全不可行的。acspecialac

如果我在有 的边的地方添加一条IS_SPECIAL边，那么查询就会变得非常快，允许我在一秒内推回大约 100 代。PARENT_OF{special: true}

此查询创建所有新边：

match (a)-[r:PARENT_OF {special: true}]->(b) 
create (a)-[:IS_SPECIAL]->(b);

只需不到一秒的时间即可在图表中添加 91K 个关系。

然后

match (c {is_interesting: true}) 
with c 
match (a)-[:IS_SPECIAL*]->(c) 
return distinct a;

只需不到一秒的时间即可找到从唯一目标节点返回的“特殊”路径上的 112 个节点c。首先匹配c并限制使用的节点集with c似乎也很重要，因为 Neo4J 似乎也没有对节点属性进行预过滤，并且如果有几个“有趣的”目标节点，事情会变得更慢。