PathFinder: A unified approach for handling paths in graph query languages
Cet article introduit PathFinder, une approche unifiée et hautement efficace pour le traitement des requêtes de chemin dans les langages de graphes modernes qui exploite une représentation de chemin compacte et une exécution pipelinée pour atteindre des performances stables et surpasser les moteurs de graphes existants d'un ordre de grandeur.
Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète
Imaginez que vous explorez une ville magique et immense appelée Graph City. Dans cette ville, chaque personne est un bâtiment (un nœud), et chaque relation entre elles est une route (une arête) avec un panneau spécifique dessus, comme « suit », « habite » ou « travaille ».
Pendant des années, les guides touristiques de la ville (les anciens moteurs de bases de données) avaient une règle étrange : si vous demandiez : « Montrez-moi tous les chemins pour aller de Joe à la Tour Eiffel en ne prenant que des routes de type "suit" », le guide se contentait de pointer du doigt et de dire : « D'accord, vous pouvez y arriver ! », puis s'arrêtait là. Il vous donnait la destination, mais il ne vous montrait pas la carte du voyage.
C'est un problème pour les détectives. Si vous essayez de résoudre un mystère (comme repérer le blanchiment d'argent ou suivre une rumeur), vous ne voulez pas seulement savoir qui est connecté ; vous avez besoin de voir l'intégralité du chemin emprunté. Est-ce un trajet direct ? Est-ce qu'on a fait trois fois le tour ? Est-ce qu'on a pris un raccourci ?
Entrez dans l'histoire de PathFinder, un nouveau guide touristique super intelligent conçu par Benjamín, Wim, Carlos et Domagoj. Ce document présente PathFinder, le premier guide capable non seulement de vous dire qui est connecté, mais aussi de vous remettre la carte exacte de chaque itinéraire possible, peu importe la complexité des règles.
La magie du « Graphe Produit »
Comment PathFinder fait-il cela sans se perdre dans un labyrinthe ? Imaginez que vous avez une carte régulière de la ville, et que vous possédez également une petite liste de contrôle magique (un automate) qui dit : « Vous devez prendre une route "suit", puis une autre route "suit", puis une route "travaille" ».
PathFinder ne se contente pas de marcher dans la ville ; il construit une ville fantôme (appelée Graphe Produit) où chaque bâtiment est une combinaison d'un bâtiment de la ville réelle et d'une étape de la liste de contrôle.
- Si vous êtes à « Joe » et que vous avez effectué zéro étape, vous êtes à
(Joe, Étape 0). - Si vous prenez une route « suit » vers « Paul », vous passez à
(Paul, Étape 1).
En marchant à travers cette ville fantôme, PathFinder peut instantanément voir quels itinéraires correspondent à votre liste de contrôle. C'est comme avoir un GPS qui n'éclaire que les routes sur lesquelles vous êtes autorisé à conduire, ignorant toutes les autres.
Les 27 façons de marcher
Le document explique qu'il existe 27 règles différentes (appelées « modes ») pour la façon dont vous pouvez circuler dans Graph City. PathFinder est le premier moteur capable de gérer ces 27 modes. Voici quelques-unes de ces variantes :
- WALK (Marche) : Vous pouvez aller n'importe où, même si vous faites des cercles ou visitez la même maison deux fois. (C'est le plus facile, mais cela peut mener à des boucles infinies !).
- TRAIL (Sentier) : Vous pouvez visiter la même maison deux fois, mais vous ne pouvez pas emprunter la même route deux fois.
- SIMPLE (Simple) : Vous ne pouvez pas visiter la même maison deux fois (à moins de partir et d'arriver au même endroit). C'est la règle la plus difficile à suivre car le nombre de chemins possibles peut exploser.
- ANY SHORTEST (N'importe quel plus court) : Donnez-moi simplement un seul des itinéraires les plus rapides.
- ALL SHORTEST (Tous les plus courts) : Donnez-moi chaque itinéraire qui est le plus rapide.
- SHORTEST k GROUPS (Groupes de k plus courts) : Donnez-moi les itinéraires les plus rapides, puis le deuxième groupe d'itinéraires les plus rapides, et ainsi de suite, jusqu'à groupes.
Les auteurs démontrent que, bien que certaines de ces règles (comme trouver un chemin « Simple ») soient théoriquement très difficiles — si difficiles que les ordinateurs abandonnent généralement sur de grandes cartes — PathFinder les gère étonnamment bien dans le monde réel.
Le problème de la « Boucle Infinie »
Un gros casse-tête dans Graph City est que s'il y a une boucle (par exemple, Joe suit Paul, et Paul suit Joe), vous pourriez tourner en rond dans cette boucle éternellement. Si vous demandez « tous les chemins », la réponse est infinie !
Pour corriger cela, les standards GQL et SQL/PGQ (les livres de règles de ces langages) permettent de choisir un mode comme « Simple » ou « Trail » pour arrêter les boucles infinies. PathFinder respecte parfaitement ces règles. Il sait exactement quand arrêter l'exploration d'un chemin pour ne pas rester coincé dans un cercle sans fin, tout en trouvant tous les chemins valides que vous avez demandés.
Le test de vitesse : PathFinder contre les autres
Les auteurs n'ont pas seulement construit PathFinder ; ils l'ont mis à l'épreuve face aux grands noms de l'industrie : Neo4j, Nebula, Kuzu, Jena, Blazegraph et Virtuoso.
Ils ont effectué des tests sur trois scénarios différents :
- Pokec : Un réseau social de taille moyenne avec 1,6 million de personnes et 30 millions de connexions.
- Wikidata : Un graphe de connaissances gigantesque du monde réel avec 364 millions de nœuds et 1,257 milliard d'arêtes.
- Diamond : Un graphe mathématique complexe conçu pour présenter un nombre exponentiel de chemins (spécifiquement, chemins).
Les résultats :
- Vitesse : PathFinder était 10 à 100 fois plus rapide que les autres moteurs dans presque tous les tests.
- Stabilité : Alors que les autres moteurs commençaient à planter ou à expirer (abandonner) lorsque les chemins devenaient plus longs ou plus complexes, Pathifer continuait de fonctionner sans faiblir.
- La surprise de l'« Intraitabilité » : Pour les modes « Simple » et « Trail », la théorie veut que l'ordinateur mette une éternité à trouver la réponse. Pourtant, lors des tests en conditions réelles (comme sur Wikidata), PathFinder a trouvé 100 000 chemins rapidement. Les auteurs suggèrent que cela est dû au fait que les données du monde réel ne possèdent généralement pas la « tempête parfaite » de connexions qui fait exploser les mathématiques.
Ce que PathFinder ne fait PAS (encore)
Il est important de savoir ce que ce document ne prétend pas :
- Il ne dit pas que PathFinder est magique. Si vous demandez chaque chemin possible dans un graphe avec des boucles, la réponse est toujours infinie, et aucun ordinateur ne peut imprimer cela. PathFinder se contente de s'arrêter à une limite que vous définissez (comme 100 000 résultats).
- Il ne prétend pas avoir résolu le problème du « Chemin Simple » pour tous les graphes possibles. Le document admet que, dans les pires scénarios théoriques, trouver un chemin simple est toujours NP-complet (une façon sophistiquée de dire « très difficile sur le plan computationnel »). PathFinder fonctionne simplement mieux que les autres sur les graphes que nous utilisons réellement dans la vie courante.
- Il ne prétend pas non plus avoir résolu le mode « Simple » pour RDF (un type spécifique de format de données) pour le moment. Les auteurs précisent qu'ils n'ont pas encore implémenté le mode « Trail » pour RDF car il n'est pas clair comment définir un « sentier » lorsque les arêtes n'ont pas de noms uniques.
L'essentiel à retenir
PathFinder est un nouveau moteur qui agit comme un guide touristique surpuissant. Il peut prendre un ensemble de règles complexes (comme « Trouvez tous les chemins de Joe à ENS Paris qui suivent le schéma "suit" puis "travaille" ») et renvoyer les cartes réelles de ces voyages.
Les auteurs ont mesuré cela sur des données réelles et ont constaté que PathFinder est significativement plus rapide et plus stable que les bases de données orientées graphes de haut niveau actuelles. Ils ont même montré que PathFinder peut être ajouté à des systèmes existants (comme les moteurs SPARQL) pour leur donner ce nouveau superpouvoir. Bien que les mathématiques disent que certaines de ces tâches sont impossibles à réaliser rapidement, dans le désordre du monde réel, PathFinder prouve que cela peut être fait avec une rapidité remarquable.
Noyé(e) sous les articles dans votre domaine ?
Recevez des digests quotidiens des articles les plus récents correspondant à vos mots-clés de recherche — avec des résumés techniques, dans votre langue.