PathFinder: A unified approach for handling paths in graph query languages
Dit artikel introduceert PathFinder, een uniforme en uiterst efficiënte benadering voor het verwerken van padvragen in moderne grafentalen die gebruikmaakt van compacte padrepresentatie en gepipeloteerde executie om stabiele prestaties te bereiken en bestaande grafengeneratoren met een orde van grootte te overtreffen.
Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer
Stel je voor dat je een enorme, magische stad verkent genaamd Graph City. In deze stad is elke persoon een gebouw (een node), en elke relatie tussen hen is een weg (een edge) met een specifiek bordje erop, zoals "volgt", "woont in" of "werkt bij".
Jarenlang hadden de stadstoursgidsen (de oude database-engines) een vreemde regel: als je vroeg: "Laat me alle manieren zien waarop ik van Joe naar de Eiffeltoren kan komen door alleen 'volgt'-wegen te nemen," wees de gids alleen maar aan en zei: "Oké, je kunt er komen!" en stopte dan. Ze gaven je de bestemming, maar ze zouden je niet de kaart van de reis laten zien.
Dit is een probleem voor detectives. Als je een mysterie probeert op te lossen (zoals het opsporen van witwaspraktijken of het volgen van een gerucht), wil je niet alleen weten wie met wie verbonden is; je moet ook de volledige route kunnen zien die ze hebben afgelegd. Gingen ze rechtstreeks naar daar? Liepen ze drie keer rondjes? Pakten ze een kortere route?
Maak kennis met PathFinder, een nieuwe, superintelligente gids gebouwd door Benjamín, Wim, Carlos en Domagoj. Dit paper introduceert PathFinder, de eerste gids die niet alleen kan vertellen wie verbonden is, maar je ook de exacte kaart van elke mogelijke route kan overhandigen, ongeacht hoe ingewikkeld de regels ook zijn.
De Magie van de "Product Graph"
Hoe doet PathFinder dit zonder de weg kwijt te raken in een doolhof? Stel je voor dat je een gewone kaart van de stad hebt, en dat je ook een kleine, magische checklist (een automaat) hebt die zegt: "Je moet een 'volgt'-weg nemen, dan nog een 'volgt'-weg, en dan een 'werkt bij'-weg."
PathFinder loopt niet alleen door de stad; het bouwt een schaduwstad (een Product Graph genoemd) waar elk gebouw een combinatie is van een echt stadsgebouw en een stap op de checklist.
- Als je bij "Joe" bent en nul stappen hebt gezet, ben je op
(Joe, Stap 0). - Als je een "volgt"-weg neemt naar "Paul", beweeg je naar
(Paul, Stap 1).
Door door deze schaduwstad te wandelen, kan PathFinder direct zien welke routes overeenkomen met jouw checklist. Het is alsof je een GPS hebt die alleen de wegen oplicht waar je op staat om te rijden, en de rest negeert.
De 27 Manieren om te Wandelen
Het paper legt uit dat er 27 verschillende regels (modi) zijn voor hoe je door Graph City kunt wandelen. PathFinder is de eerste engine die alle 27 van deze regels kan afhandelen. Hier zijn enkele van de smaken:
- WALK (Wandeling): Je kunt overal heen gaan, zelfs als je rondjes loopt of twee keer hetzelfde huis bezoekt. (Dit is de makkelijkste, maar kan leiden tot oneindige lussen!).
- TRAIL (Spoor): Je kunt hetzelfde huis twee keer bezoeken, maar je kunt niet twee keer over dezelfde weg lopen.
- SIMPLE (Eenvoudig): Je kunt niet hetzelfde huis twee keer bezoeken (tenzij je begint en eindigt op dezelfde plek). Dit is de moeilijkste regel te volgen omdat het aantal mogelijke paden kan exploderen.
- ANY SHORTEST (Enige kortste): Geef me gewoon één van de snelste routes.
- ALL SHORTEST (Alle kortste): Geef me elke route die de snelste is.
- SHORTEST k GROUPS (Kortste k groepen): Geef me de snelste routes, en dan de tweede-snelste groep routes, enzovoort, tot aan de -de groep.
De auteurs laten zien dat hoewel sommige van deze regels (zoals het vinden van een "Simple" pad) theoretisch zeer moeilijk zijn — zo moeilijk dat computers meestal opgeven bij enorme kaarten — PathFinder ze in de echte wereld verrassend goed afhandelt.
Het "Oneindige Lus"-probleem
Een groot hoofdpijngeval in Graph City is dat als er een lus is (zoals Joe volgt Paul, en Paul volgt Joe), je eeuwig rond dat rondje kunt lopen. Als je vraagt om "alle wandelingen", is het antwoord oneindig!
Om dit op te lossen, laten de GQL en SQL/PGQ-standaarden (de regelboeken voor deze talen) je een modus kiezen zoals "Simple" of "Trail" om de oneindige lussen te stoppen. PathFinder respecteert deze regels perfect. Het weet precies wanneer het moet stoppen met het verkennen van een pad zodat het niet vast komt te zitten in een eindeloze cirkel, terwijl het nog steeds alle geldige paden vindt waar je om vroeg.
De Snelheidstest: PathFinder versus de Rest
De auteurs hebben PathFinder niet alleen gebouwd; ze hebben het getest tegen de grote namen in de industrie: Neo4j, Nebula, Kuzu, Jena, Blazegraph en Virtuoso.
Ze voerden tests uit in drie verschillende scenario's:
- Pokec: Een middelgroot sociaal netwerk met 1,6 miljoen mensen en 30 miljoen verbindingen.
- Wikidata: Een gigantische real-world kennisgraaf met 364 miljoen nodes en 1,257 miljard edges.
- Diamond: Een lastige, wiskundig geconstrueerde graaf die ontworpen is om een exponentieel aantal paden te hebben (specifiek, paden).
De Resultaten:
- Snelheid: PathFinder was in bijna elke test 10 tot 100 keer sneller dan de andere engines.
- Stabiliteit: Terwijl andere engines begonnen te crashen of te timen (opgeven) wanneer paden langer of complexer werden, bleef PathFinder gestaag doorgaan.
- De "Intractable" Verrassing: Voor de "Simple" en "Trail" modi zegt de theorie dat de computer er eeuwig over zou doen om het antwoord te vinden. Maar in de real-world tests (zoals op Wikidata) vond PathFinder snel 100.000 paden. De auteurs suggereren dat dit komt omdat echte data meestal niet de specifieke "perfecte storm" aan verbindingen heeft die de wiskunde laat exploderen.
Wat PathFinder (nog) NIET doet
Het is belangrijk om te weten wat dit paper niet claimt:
- Het zegt niet dat PathFinder magisch is. Als je om elk enkel pad in een graaf met lussen vraagt, is het antwoord nog steeds oneindig, en geen enkele computer kan dat printen. PathFinder stopt gewoon bij een limiet die je instelt (zoals 100.000 resultaten).
- Het claimt niet dat het het "Simple Path"-probleem voor alle mogelijke grafen heeft opgelost. Het paper geeft toe dat in de slechtste theoretische scenario's het vinden van een simpel pad nog steeds NP-compleet is (een chique manier om te zeggen: "computationeel zeer moeilijk"). PathFinder werkt gewoon beter dan de rest op de grafen die we daadwerkelijk in het echte leven gebruiken.
- Het claimt nog niet de "Simple" modus voor RDF (een specifiek type dataformaat) te hebben opgelost. De auteurs zeggen dat ze de "Trail" modus voor RDF nog niet hebben geïmplementeerd omdat het onduidelijk is hoe je een "trail" definieert wanneer edges geen unieke namen hebben.
De Kern van het Verhaal
PathFinder is een nieuwe engine die fungeert als een superkrachtige stadstourguide. Het kan een complexe set regels aan (zoals "Zoek alle paden van Joe naar ENS Paris die het patroon 'volgt' gevolgd door 'werkt' volgen") en de werkelijke kaarten van die reizen teruggeven.
De auteurs hebben dit gemeten op echte data en ontdekten dat PathFinder aanzienlijk sneller en stabieler is dan de huidige top-tier graph databases. Ze hebben zelfs aangetoond dat het aan bestaande systemen (zoals SPARQL-engines) kan worden toegevoegd om hen deze nieuwe superkracht te geven. Hoewel de wiskunde zegt dat sommige van deze taken onmogelijk snel uitgevoerd kunnen worden, bewijst PathFinder in de rommelige echte wereld dat het met een opmerkelijke snelheid kan worden gedaan.
Verdrinkt u in papers in uw vakgebied?
Ontvang dagelijkse digests van de nieuwste papers die bij uw onderzoekswoorden passen — met technische samenvattingen, in uw taal.