如何使用 Gremlin 提高最短路径的性能？

Question

我将 JanusGraph 与 Gremlin 和 this 数据集一起使用，该数据集包含 2.6k 个节点和 6.6k 个边（两侧各有 3.3k 个边）。我已经运行查询了 10 分钟而没有找到最短路径。

使用 Gephi 的最短路径几乎是瞬时的。

这是我的查询：

g.V(687).repeat(out().simplePath()).until(hasId(1343)).path().limit(1)

Answer 1

对于 simplePath()，您的查询仍然处理比必要的多得多的路径。例如，如果 688 是 687 的直接邻居，也是 1000 的邻居，在另一条路径上相距 10 跳，为什么要遵循 1000 的路径？ =16=] 到 688，如果你早就看过这个十字路口了？

所以，你应该过滤掉你以前见过的任何十字路口（第一次出现的总是最近的）：

g.V(687).store('x').
  repeat(out().where(without('x')).aggregate('x')).
   until(hasId(1343)).limit(1).path()

另请注意，我交换了 limit(1) 和 path；那是因为先收集所有路径然后只采用第一个是资源（CPU 和内存）的浪费。

更新：

如果其他人想尝试一下，这里是将数据集加载到 TinkerGraph 的代码：

g = TinkerGraph.open().traversal()
"http://nrvis.com/download/data/road/road-minnesota.zip".toURL().withInputStream {
  new java.util.zip.ZipInputStream(it).with {
    while (entry = it.getNextEntry()) {
      if ("road-minnesota.mtx" == entry.getName()) {
        it.eachLine {
          if (it ==~ /[0-9]+ [0-9]+/) {
            def (a, b) = it.split()*.toInteger()
            g.V(a).fold().
              coalesce(unfold(), addV().property(id, a)).
              addE("road").
                to(V(b).fold().coalesce(unfold(), addV().property(id, b))).inV().
              addE("road").to(V(a)).iterate()
          }
        }
        break
      }
      it.closeEntry()
    }
  }
}

以及查询和一点基准：

gremlin> g.V(687).store('x').
......1>   repeat(out().where(without('x')).aggregate('x')).
......2>    until(hasId(1343)).limit(1).
......3>   path().by(id)
==>[687,689,686,677,676,675,673,626,610,606,607,608,735,732,733,730,729,734,737,738,739,742,786,816,840,829,815,825,865,895,872,874,968,983,1009,1044,1140,1142,1148,1219,1255,1329,1337,1339,1348,1343]

gremlin> clock (100) {
......1>   g.V(687).store('x').
......2>     repeat(out().where(without('x')).aggregate('x')).
......3>      until(hasId(1343)).limit(1).
......4>     path().iterate()
......5> }
==>12.5362714

TinkerGraph 上的 12.5 毫秒对我来说相当不错。预计在 JG 上运行会稍微长一点，但肯定不会超过 10 分钟。

如何使用 Gremlin 提高最短路径的性能？

How to increase performance of shortest path using Gremlin?

graph

shortest-path

cassandra

gremlin

janusgraph