1

我正在尝试使用 graphrepository 在 spring-neo4j 中创建一个应用程序。其中一个要求是在两个子节点之间找到一个最低公共祖先 (lca)。

目前我使用以下查询来实现这一点：

 @Query("MATCH path = (c1:Concept)-[r:Relation*{type: 'Is a'}]->(ca:Concept)<-[r:Relation*{type: 'Is a'}]-(c2:Concept) 
      WHERE c1.conceptID = {conceptId1} AND c2.conceptID = {conceptId2}
      RETURN ca ORDER BY length(path) LIMIT 1")

Concept findLowestCommonAncestor(@Param("conceptId1") Long conceptId1, @Param("conceptId2") Long conceptId2);

这里的问题是性能。最初我的图表由 330 000 个节点和 2 000 000 个关系组成。我感兴趣的关系是具有类型的关系：“Is a”。它们仅在树中向上移动（连接子节点与父节点）。最大向上距离为 3。

这是树结构：

树结构示例

因为我有几个像这样的树结构，所以我决定添加一个根节点，将所有不同的树结构连接在一起。以便始终找到 lca。但是添加这个根节点极大地改变了我的性能：从 558 毫秒到 562286 毫秒

我知道添加根节点会影响性能，但它不应该这么多，对吧？如果是这样，是否有更好的方法来计算 lca？

我认为我的密码查询只会在树中向上查找节点。所以在这种情况下，添加一个额外的根节点不应该对性能产生这么大的影响。

4

2 回答 2

1

首先，我要感谢@Supamiu 对我的问题的帮助。

尽管他的回答对于某些情况可能就足够了。就我而言，实际上不可能更改模型。

令人惊讶的是，我仅通过更改密码查询就设法提高了性能。

我原来的查询：

MATCH path = (c1:Concept)-[r1:Relation*{type: "Is a"}]->(ca:Concept)<-[r2:Relation*{type: "Is a"}]-(c2:Concept)
WHERE c1.conceptID=35104066 AND c2.conceptID=35808913
RETURN ca
ORDER BY length(path)
LIMIT 1

简介：http: //i.imgur.com/14yleCo.png

我将其更改为：

MATCH (c1:Concept {conceptID: 35104066})-[:Relation*{type: "Is a"}]->(p1:Concept)
MATCH (:Concept {conceptID: 35808913})-[:Relation*{type: "Is a"}]->(p2:Concept)
WHERE p1.conceptID = p2.conceptID
MATCH path = (c1)-[:Relation*{type: "Is a"}]->(p1)
RETURN p1
ORDER BY length(path)
LIMIT 1

简介：http: //imgur.com/YCDDF5H

这使我在大约 100 毫秒内获得了最低共同祖先，这是一个显着的改进！

我仍然不完全明白为什么这会产生如此大的差异。但我认为其中一个原因是我使用了树形结构。我认为在第二个查询中，Cypher 只在树中向上搜索，导致搜索关系减少。因此，我认为，在 blob 结构中，这并没有真正的帮助。

有人可以证实这一点吗？

于 2016-02-25T12:34:42.403 回答
0

您的问题是关系标签问题，让我解释一下：

首先，您的请求与无限深度的:Relation关系相匹配。

您说数据库中的每棵树现在都与一个根节点相关，我猜它使用:Relation关系与根节点相关。

因此，当您匹配每个标记:Relation为无限深度的关系时，它会在过滤type属性之前匹配数据库中的每个关系。这就是为什么这个根节点添加了这样一个性能问题，因为它以相同的关系将每个节点连接在一起。

如何解决？

更改您的关系标签，使用它们而不是与属性匹配：

(ca:Concept{properties...})-[:IS_A]->(ca2:Concept)

并使用另一个关系标签将您的顶部树节点链接到根节点。

然后，当您使用无限深度请求匹配节点时，您将能够使用标签进行匹配，从而避免您实际遇到的问题。

另一种解决方案是在查询中添加最大深度，因为您的树最多为 3 级，您可以将关系深度限制为 3。但我认为第一个解决方案要好得多，因为只创建一种类型的关系和过滤在 neo4j 中使用它们的属性是一种不好的做法。

编辑

因此，这是您的第一个个人资料：http: //i.imgur.com/xskg39J.png

您可以在这里看到匹配[:Relation*]在被过滤之前有 31,328 个匹配，这非常好。

在第二个配置文件（带有根节点）上：http: //i.imgur.com/14yleCo.png

您可以看到相同的匹配获得了近 2,000,000 次点击，经过过滤后达到 500,000 次……这太多了。

我认为解决方案是路径，你可以看看这个：

仅通过“更好”的密码查询无法解决该问题。我认为您的问题可以通过更好的数据模型来解决，但是如果不从事项目本身就很难找到哪一个。我能提供的唯一想法是指南： http: //neo4j.com/developer/guide-data-modeling/

于 2016-02-23T14:44:14.867 回答