PathFinder: A unified approach for handling paths in graph query languages
Dieses Paper stellt PathFinder vor, einen vereinheitlichten und hocheffizienten Ansatz zur Verarbeitung von Pfadabfragen in modernen Graphsprachen, der eine kompakte Pfadrepräsentation sowie pipelined Ausführung nutzt, um eine stabile Performance zu erreichen und bestehende Graph-Engines um eine Größenordnung zu übertreffen.
Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen
Stellen Sie sich vor, Sie erkunden eine riesige, magische Stadt namens Graph City. In dieser Stadt ist jeder Mensch ein Gebäude (ein Knoten) und jede Beziehung zwischen ihnen ist eine Straße (eine Kante) mit einem speziellen Schild darauf, wie zum Beispiel „folgt“, „lebt“ oder „arbeitet“.
Jahrelang hatten die Stadtführer (die alten Datenbank-Engines) eine seltsame Regel: Wenn man sie fragte: „Zeig mir alle Wege, wie ich von Joe zum Eiffelturm komme, indem ich nur ‚folgt‘-Straßen nehme“, zeigte der Führer nur auf den Punkt und sagte: „Okay, du kommst dort an!“, und hörte dann auf. Er gab einem das Ziel, aber er zeigte einem nicht die Karte der Reise.
Das ist ein Problem für Detektive. Wenn man versucht, ein Rätsel zu lösen (wie etwa Geldwäsche aufzuspüren oder ein Gerücht zu verfolgen), will man nicht nur wissen, wer miteinander verbunden ist; man muss die gesamte Route sehen, die sie genommen haben. Sind sie direkt dorthin gegangen? Sind sie dreimal im Kreis gelaufen? Haben sie eine Abkürzung genommen?
Hier kommt PathFinder ins Spiel, ein neuer, super-intelligenter Stadtführer, der von Benjamín, Wim, Carlos und Domagoj entwickelt wurde. Dieses Paper stellt PathFinder vor, den ersten Guide, der nicht nur sagen kann, wer verbunden ist, sondern einem auch die exakte Karte jeder möglichen Route überreichen kann, egal wie kompliziert die Regeln sind.
Die Magie des „Produkts-Graphen“
Wie schafft es PathFinder, dies zu tun, ohne sich in einem Labyrinth zu verl Erstirren? Stellen Sie sich vor, Sie haben eine normale Karte der Stadt und zusätzlich eine winzige, magische Checkliste (einen Automaten), die besagt: „Du musst eine ‚folgt‘-Straße nehmen, dann noch eine ‚folgt‘-Straße und dann eine ‚arbeitet‘-Straße.“
PathFinder läuft nicht einfach nur durch die Stadt; es baut eine Schattenstadt (einen sogenannten Produkts-Graphen), in der jedes Gebäude eine Kombination aus einem echten Stadtgebäude und einem Schritt auf der Checkliste ist.
- Wenn Sie bei „Joe“ sind und null Schritte gemacht haben, befinden Sie sich bei
(Joe, Schritt 0). - Wenn Sie eine „folgt“-Straße zu „Paul“ nehmen, bewegen Sie sich zu
(Paul, Schritt 1).
Indem PathFinder durch diese Schattenstadt wandert, kann es sofort erkennen, welche Routen zu Ihrer Checkliste passen. Es ist wie ein GPS, das nur die Straßen aufleuchten lässt, auf denen man fahren darf, und den Rest ignoriert.
Die 27 Arten zu wandern
Das Paper erklärt, dass es 27 verschiedene Regeln (sogenannte „Modi“) dafür gibt, wie man durch Graph City wandern kann. PathFinder ist die erste Engine, die alle 27 davon bewältigen kann. Hier sind einige der Varianten:
- WALK (Wandern): Sie können überallhin gehen, selbst wenn Sie im Kreis laufen oder dasselbe Haus mehrmals besuchen. (Dies ist der einfachste Modus, kann aber zu unendlichen Schleifen führen!).
- TRAIL (Pfad): Sie können dasselbe Haus mehrmals besuchen, aber Sie dürfen nicht dieselbe Straße zweimal benutzen.
- SIMPLE (Einfach): Sie dürfen nicht dasselbe Haus zweimal besuchen (es sei denn, Sie starten und enden am selben Ort). Dies ist die schwerste Regel zu befolgen, da die Anzahl der möglichen Pfade explodieren kann.
- ANY SHORTEST (Jeder kürzeste): Gib mir einfach einen der schnellsten Wege.
- ALL SHORTEST (Alle kürzesten): Gib mir jeden einzelnen Weg, der der schnellste ist.
- SHORTEST k GROUPS (Kürzeste k Gruppen): Gib mir die schnellsten Wege, dann die zweitschnellste Gruppe von Wegen und so weiter, bis zu Gruppen.
Die Autoren zeigen, dass obwohl einige dieser Regeln (wie das Finden eines „Simple“-Pfades) theoretisch sehr schwer sind – so schwer, dass Computer bei riesigen Karten normalerweise aufgeben – PathFinder sie in der realen Welt erstaunlich gut bewältigt.
Das Problem der „Endlosschleife“
Ein großes Problem in Graph City ist, dass es, wenn es eine Schleife gibt (wie Joe folgt Paul, und Paul folgt Joe), man ewig um diese Schleife herumwandern könnte. Wenn man nach „allen Walks“ fragt, ist die Antwort unendlich!
Um dies zu lösen, lassen die GQL- und SQL/PGQ-Standards (die Regelbücher dieser Sprachen) zu, dass man einen Modus wie „Simple“ oder „Trail“ wählt, um die Endlosschleifen zu stoppen. PathFinder respektiert diese Regeln perfekt. Es weiß genau, wann es aufhören muss, einen Pfad zu erkunden, damit es nicht in einem endlosen Kreis stecken bleibt, während es dennoch alle gültigen Pfade findet, nach denen Sie gefragt haben.
Der Geschwindigkeitstest: PathFinder gegen den Rest
Die Autoren haben PathFinder nicht nur gebaut; sie haben ihn gegen die großen Namen der Branche getestet: Neo4j, Nebula, Kuzu, Jena, Blazegraph und Virtuoso.
Sie führten Tests in drei verschiedenen Szenarien durch:
- Pokec: Ein mittelgroßes soziales Netzwerk mit 1,6 Millionen Menschen und 30 Millionen Verbindungen.
- Wikidata: Ein gigantischer realer Wissensgraph mit 364 Millionen Knoten und 1,257 Milliarden Kanten.
- Diamond: Ein kniffliger, mathematisch konstruierter Graph, der darauf ausgelegt ist, eine exponentielle Anzahl von Pfaden zu besitzen (speziell Pfade).
Die Ergebnisse:
- Geschwindigkeit: PathFinder war in fast jedem Test 10 bis 100 Mal schneller als die anderen Engines.
- Stabilität: Während andere Engines abstürzten oder Timeouts verursachten (aufgaben), wenn die Pfade länger oder komplexer wurden, arbeitete PathFinder stetig weiter.
- Die „Intraktabilität“-Überraschung: Für die Modi „Simple“ und „Trail“ besagt die Theorie, dass der Computer ewig bräuchte, um die Antwort zu finden – so lange, dass er normalerweise aufgibt. Aber in den realen Tests (wie bei Wikidata) fand PathFinder 100.000 Pfade sehr schnell. Die Autoren vermuten, dass dies daran liegt, dass reale Daten normalerweise nicht über die spezifische „perfekte Sturmwolke“ an Verbindungen verfügen, die die Mathematik explodieren lässt.
Was PathFinder (noch) NICHT tut
Es ist wichtig zu wissen, was dieses Paper nicht behauptet:
- Es behauptet nicht, dass PathFinder magisch ist. Wenn Sie nach jedem einzelnen Pfad in einem Graphen mit Schleifen fragen, ist die Antwort immer noch unendlich, und kein Computer kann das ausdrucken. PathFinder hält sich einfach an ein Limit, das Sie setzen (wie z. B. 100.000 Ergebnisse).
- Es behauptet nicht, das „Simple Path“-Problem für alle möglichen Graphen gelöst zu haben. Das Paper gibt zu, dass das Finden eines einfachen Pfades in den theoretischen Worst-Case-Szenarien immer noch NP-vollständig ist (ein Fachbegriff dafür, dass es rechnerisch „sehr schwer“ ist). PathFinder funktioniert einfach besser als alle anderen auf den Graphen, die wir tatsächlich verwenden.
- Es behauptet nicht, den „Simple“-Modus für RDF (ein spezielles Datentyp-Format) bereits gelöst zu haben. Die Autoren sagen, dass sie den „Trail“-Modus für RDF noch nicht implementiert haben, da unklar ist, wie man einen „Trail“ definiert, wenn Kanten keine eindeutigen Namen haben.
Das Fazit
PathFinder ist eine neue Engine, die wie ein super-mächtiger Stadtführer fungiert. Sie kann ein komplexes Set von Regeln (wie „Finde alle Pfade von Joe zu ENS Paris, die dem Muster ‚folgt‘ dann ‚arbeitet‘ folgen“) nehmen und die tatsächlichen Karten dieser Reisen zurückgeben.
Die Autoren haben dies mit realen Daten gemessen und festgestellt, dass PathFinder signifikant schneller und stabiler ist als aktuelle Top-Graph-Datenbanken. Sie haben sogar gezeigt, dass man PathFinder in bestehende Systeme (wie SPARQL-Engines) integrieren kann, um diesen das neue Supertalent zu verleihen. Während die Mathematik sagt, dass einige dieser Aufgaben unmöglich schnell zu lösen sind, beweist PathFinder in der chaotischen, realen Welt, dass dies mit bemerkenswerter Geschwindigkeit möglich ist.
Ertrinken Sie in Arbeiten in Ihrem Fachgebiet?
Erhalten Sie tägliche Digests der neuesten Arbeiten passend zu Ihren Forschungsbegriffen — mit technischen Zusammenfassungen, in Ihrer Sprache.