Как повысить производительность по кратчайшему пути с помощью Gremlin? - PullRequest
Новая
       69

Как повысить производительность по кратчайшему пути с помощью Gremlin?

0 голосов
/ 08 мая 2018

Я использую JanusGraph с Gremlin и этот набор данных, охватывающий 2,6 тыс. Узлов и 6,6 тыс. Ребер (3,3 тыс. Ребер с обеих сторон). Я выполнил запрос в течение 10 минут, не найдя кратчайшего пути.

При использовании Gephi кратчайший путь почти мгновенный.

Вот мой запрос: 

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

1 Ответ

0 голосов
/ 11 мая 2018

С simplePath() ваш запрос по-прежнему обрабатывает гораздо больше путей, чем необходимо. Например, если 688 является непосредственным соседом 687, но также соседом 1000, который находится в 10 прыжках на другом пути, почему вы хотите следовать по пути от 1000 до 688 , если вы уже видели этот перекресток гораздо раньше?

Итак, вы должны отфильтровать любой перекресток, который вы видели ранее (первое вхождение всегда самое близкое): 

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

Также обратите внимание, что я поменял местами limit(1) и path; это потому, что это пустая трата ресурсов (ЦП и память), чтобы сначала собрать все пути, а затем просто выбрать первый.

UPDATE:

Если другие захотят попробовать, вот код для загрузки набора данных в 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

12,5 мс на TinkerGraph выглядит довольно хорошо для меня. Ожидайте, что он будет работать на JG немного дольше, но, конечно, не более 10 минут.

...