Shortestpath mit komplexen Kriterien ist es möglich, in jedem Diagramm DBMS

Question

Im Moment bin ich mit Neo4j und löste die Aufgabe von der falschen Seite. Zuerst bekomme ich allShortestPaths und dann nach den richtigen in ihnen mit Java suchen. Natürlich kann dieser Weg keine Ergebnisse garantieren, selbst wenn sie existieren. Also, ich suche nach irgendeinem Graph DBMS, das nativ suchen kann, was ich brauche.

Datenmodell ist einfach:

• Knoten: keine Eigenschaften mit Ausnahme Nummer zur Identifizierung

• Relations: 1 Objekt mit Doppel Wert

Um es klar zu machen - es ist eine Liste der Organisationen und Anteile, die sie besitzen (dh Eigenschaft = Prozentsatz> 0 < = 100) .

Kriterien, wenn durch den Weg gehen ist:

• Wenn nächste Beziehung 50 ++ der Knoten enthalten ist (Pfad weiter)
• Wenn nächste Beziehung weniger ist, dann 50, aber alle bereits Knoten in Pfad eigen 50+ dieses Knotens, dann noch weiter der Weg

das bedeutet, soll dieser Algorithmus nicht nur die Beziehungen des Weges selbst, sondern „Seite“ Beziehungen (vorzugsweise nicht immer berechnen, sondern nur, wenn „nächste Beziehung "ist 50-).

Und last, but not least: Es wird erwartet, dass die Leistung der einheimischen shortestpath haben (dh mehrere Millisekunden auf 18mln Knoten + 40mln Beziehungen) oder in der Nähe. Keine Stunden oder gar Minuten. Momentan findet der kürzeste Weg Pfade mit 30-40-50 Hops in Millisekunden, das ist erstaunlich. Wenn ich mit dem Relation-Wert spiele, kann ich in wenigen Sekunden kürzeste Wege von mehreren Längen bekommen. Aber das ist keine ideale Lösung.

Ich bin nicht Neo4j Experte (noch :), von dem, was ich bisher entdeckt habe - Leistung von allsSortestPaths ist ziemlich dickes Ding. Das Hinzufügen zusätzlicher Kriterien kann die Leistung von Millisekunden auf Stunden reduzieren. Das ist nicht akzeptabel :(Weglänge von 10 ++ ist auch ein Muss.

Ich denke, dass ich zu viel will, aber nach wie vor, irgendwelche Hinweise, Ideen, Lösungen sind willkommen!

Answer 1

Für kleine Daten- Ich würde einfach Cypher vertrauen, um es mit einigen WHERE-Bedingungen (einfachste Lösung, am wenigsten effizient) zu behandeln

Die nächste beste Lösung (wenn Sie können), ist es, die Lösung "vorkompilieren" Problem so, dass einige Ledger-Knoten oder Beziehungen die Informationen speichern können, die Sie benötigen, und dass das Aktualisieren dieser Ledger einfacher ist als das vollständige Neukompilieren der Lösung, als dies der beste Weg zum Speichern und Abrufen der Informationen ist (seit dem Lesen, Du brauchst nur nee d um einen Knoten oder eine Beziehung hochzuziehen).

Aber vielleicht können Sie nicht die Lösung vereinfachen, und Sie haben nur , um das komplexe Traversal zu tun. Cypher ist gut darin, aber es ist blind gegenüber dem, was in der Datenbank ist, und kann Fakten nicht ausnutzen, die Sie kennen würden.In diesem Fall (für die beste Leistung) möchten Sie die Traversal API verwenden (es gibt auch die Java Core API für Neo4J, aber die Traversal-API ist viel einfacher und nur geringfügig langsamer)