ArcadeDB schickt Dijkstra und A* in den Schatten: 346 statt einer Million Knoten
Dijkstra vs. A* vs. Contraction Hierarchies
Auf dem Straßennetz von Florida mit 1,07 Millionen Kreuzungen vergleicht ArcadeDB drei Routenplaner von Tallahassee nach Coral Gables. Dijkstra besucht 1.029.617 Knoten, A* noch 840.138, eine Customizable Contraction Hierarchy nur 346 – bei identischem Ergebnis von 8 Stunden 18 Minuten. Die Hierarchie wird einmalig in rund sieben Sekunden aufgebaut und bei jeder Gewichtsänderung in unter einer Millisekunde nachgezogen, sodass Staus und Sperrungen als gewöhnliche Property-Updates sofort in die Route einfließen.
Das ist der Unterschied zwischen einer Routing-Funktion der Datenbank und einem Routing-Cache daneben: Es gibt kein Zeitfenster, in dem eine Abfrage eine Route über eine Straße liefert, die vor einer Sekunde gesperrt wurde.