我有一个非常大的图,其中包含数亿个节点和关系,我需要进行遍历以查找特定节点是否与包含特定属性的另一个节点连接。
数据高度互联,一对节点之间可以存在多种关系。
鉴于此操作需要在实时系统上运行,我有非常严格的时间限制,要求不超过 200 毫秒才能找到可能的结果。
所以我创建了以下 TraversalDescriptor:
TraversalDescription td = graph.traversalDescription()
.depthFirst()
.uniqueness(Uniqueness.NODE_GLOBAL)
.expand(new SpecificRelsPathExpander(requiredEdgeProperty)
.evaluator(new IncludePathWithTargetPropertyEvaluator(targetNodeProperty));
评估器检查每条路径是否结束节点是我的目标,如果是我的目标,则包括并修剪该路径,如果不是,则排除它并继续。 此外,我还对遍历所花费的时间和要查找的最大结果数设置了限制。 一切都可以在下面的代码中看到:
private class IncludePathWithTargetPropertyEvaluator implements Evaluator {
private String targetProperty;
private int results;
private long startTime, curTime, elapsed;
public IncludePathWithTargetPropertyEvaluator(String targetProperty) {
this.targetProperty = targetProperty;
this.startTime = System.currentTimeMillis();
this.results = 0;
}
public Evaluation evaluate(Path path) {
curTime = System.currentTimeMillis();
elapsed = curTime - startTime;
if (elapsed >= 200) {
return Evaluation.EXCLUDE_AND_PRUNE;
}
if (results >= 3) {
return Evaluation.EXCLUDE_AND_PRUNE;
}
String property = (String) path.endNode().getProperty("propertyName");
if (property.equals(targetProperty)) {
results = results + 1;
return Evaluation.INCLUDE_AND_PRUNE;
}
return Evaluation.EXCLUDE_AND_CONTINUE;
}
最后我编写了一个自定义 PathExpander,因为每次我们只需要遍历具有特定属性值的边:
private class SpecificRelsPathExpander implements PathExpander {
private String requiredProperty;
public SpecificRelsPathExpander(String requiredProperty) {
this.requiredProperty = requiredProperty;
}
public Iterable<Relationship> expand(Path path, BranchState<Object> state) {
Iterable<Relationship> rels = path.endNode().getRelationships(RelTypes.FOO, Direction.BOTH);
if (!rels.iterator().hasNext())
return null;
List<Relationship> validRels = new LinkedList<Relationship>();
for (Relationship rel : rels) {
String property = (String) rel.getProperty("propertyName");
if (property.equals(requiredProperty)) {
validRels.add(rel);
}
}
return validRels;
}
// not used
public PathExpander<Object> reverse() {
return null;
}
问题在于,遍历器在 200 毫秒过去后仍继续运行。
根据我的理解,评估器的行为是将使用 EXCLUDE_AND_CONTINUE 评估的每个路径的所有后续分支排入队列,并且遍历器本身不会停止,直到它访问了队列中的所有后续路径。
所以可能发生的情况是:如果我有甚至很少的具有很高度数的节点,也会导致要遍历数千条路径。
那么,有没有办法让遍历器在超时时突然停止,并返回这段时间可能找到的有效路径?
最佳答案
我会遵循以下思路:
Once the timeout was elapsed stop expanding the graph.
private class SpecificRelsPathExpander implements PathExpander {
private String requiredProperty;
private long startTime, curTime, elapsed;
public SpecificRelsPathExpander(String requiredProperty) {
this.requiredProperty = requiredProperty;
this.startTime = System.currentTimeMillis();
}
public Iterable<Relationship> expand(Path path, BranchState<Object> state) {
curTime = System.currentTimeMillis();
elapsed = curTime - startTime;
if (elapsed >= 200) {
return null;
}
Iterable<Relationship> rels = path.endNode().getRelationships(RelTypes.FOO, Direction.BOTH);
if (!rels.iterator().hasNext())
return null;
List<Relationship> validRels = new LinkedList<Relationship>();
for (Relationship rel : rels) {
String property = (String) rel.getProperty("propertyName");
if (property.equals(requiredProperty)) {
validRels.add(rel);
}
}
return validRels;
}
// not used
public PathExpander<Object> reverse() {
return null;
}
我想看看Neo4J TraversalDescription Definition可能对你也有好处。
关于java - Neo4j遍历框架超时,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30887036/