Road Network Contraction mit PostGIS
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 119 | |
| Autor | ||
| Mitwirkende | ||
| Lizenz | CC-Namensnennung 4.0 International: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/67593 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
| |
| Schlagwörter |
14
45
50
55
67
69
72
75
78
87
95
00:07
Open SourceImplementierungWeb logRoutingAlgorithmusKanteBerechnungQR-CodeImplementierungAttributierte GrammatikRouterGraphDesign by ContractProgrammbibliothekRechenbuchStandardabweichungDifferenteKomplex <Algebra>SchnittmengeZahlenbereichWeb logSoftwareentwicklerSoftwarePunktCoxeter-GruppeVorlesung/KonferenzComputeranimation
Transkript: Deutsch(automatisch erzeugt)
00:07
Ich präsentiere Felix Sommer mit dem Titel Road Network Contraction mit PostGIS. Ja, vielen Dank. Also, wie schon gesagt, es geht hier um Road Network Contraction mit PostGIS.
00:20
Und ich erkläre euch heute, wie ihr euer Routing rasend schnell machen könnt. Also ganz kurz über mich. Mein Name ist Felix Sommer. Ich bearbeite seit knapp drei Jahren als Full-Stack-Developer bei Camp2Camp. Und wie es schon im Titel steht, hier geht es um Road Network Contraction.
00:41
Und wenn ihr Performance-Probleme mit eurem Routing habt, dann solltet ihr euch das auf jeden Fall anschauen. Deswegen erkläre ich euch am Anfang, was es genau ist und wie es funktioniert. Und dann, warum ihr es wirklich einsetzen sollt. Und am Ende, womit oder mit welcher Technologie ihr das tun könnt. So, starten wir gleich rein. Und zwar, wir können sagen, ein Straßennetz wird als Graf dargestellt mit Kanten und Knoten.
01:11
Und jede Kante und Knoten hat bestimmte Attribute. Und diese Attribute könnten zum Beispiel sein, ja, die Geschwindigkeit, die Kosten oder die Dauer diese Kante zu befahren und den Namen zum Beispiel.
01:27
Und wenn wir uns jetzt überlegen, ja, was brauchen wir denn eigentlich für unseren Routing-Algorithmus? Was ist denn hier wirklich wichtig? Dann können wir uns ansehen, naja, Name hilft uns jetzt erstmal nur bei der Berechnung von der Route nicht so viel weiter.
01:42
Das heißt, was können wir machen? Wir können es einfach mal wegstreichen, einfach mal löschen. Was wir dann machen können, dann können wir uns angucken, dass wir es nach dem Attribut Speed gruppieren. Und das heißt, alle Kanten, die das gleiche, die gleiche Speedwert haben, können wir zusammen verbinden.
02:04
Was dann dabei rauskommt, ist, wir haben jetzt nur noch zwei Kanten. Das heißt, wir haben eine Kante und einen Knoten entfernen können. Und herzlichen Glückwunsch, wir haben somit unsere erste Grafenkontraktion durchgeführt. Jetzt kann man sich natürlich noch überlegen, ja, was ist, wenn wir noch die Kante A und B zusammenfügen können oder wollen?
02:29
Das können wir jetzt momentan noch nicht machen, da das Attribut Speed nicht den gleichen Wert hat. Aber vielleicht ist das Attribut Speed ja für uns eigentlich unwichtig für unseren Routing-Algorithmus.
02:42
Und hier ist es ganz besonders wichtig, dass wir uns überlegen, welche Attribute sind für uns wichtig? Was brauchen wir und was nicht? So, warum machen wir das Ganze? Wie ihr wahrscheinlich wisst, sind die meisten Algorithmen bei der Performance, wenn es darum geht,
03:00
ist es wichtig, dass die Komplexität so gut wie möglich ist. Und bei Routing-Algorithmen kommt es eigentlich immer darauf an, wie viele Kanten oder wie viele Knoten oder auch wie viele Kanten und Knoten unser Datenset beinhaltet. Das heißt, sobald wir unsere Anzahl an Knoten und Kanten reduzieren können,
03:24
wissen wir, dass die Performance von unserem Algorithmus auch besser wird. Wir haben uns jetzt überlegt, ja, dass sowas möchten wir haben, sowas brauchen wir. Unsere Anforderungen waren ganz klar, wir wollen, dass das schnell ist, soll Performance sein
03:41
und sich auch einfach in unsere bestehende Infrastruktur integrieren lassen. Und was er natürlich zulassen soll, er soll die Kontraktion auf den von uns bestimmten Attributen ausführen können. Da gab es dann verschiedene Möglichkeiten, verschiedene Technologien, die man einsetzen kann.
04:03
Und am Ende haben wir uns dafür entschieden, dass wir einfaches S-Grail mit Puskis benutzen. Und hier haben wir dann geguckt, genau diese Anforderungen, die wir hatten, gab es leider noch nicht in der Standard-Library von Puskis.
04:21
Deswegen haben wir dann eine Custom-Implementierung gemacht. Also, nochmal ganz kurz zusammengefasst, wenn ihr Performance-Probleme habt, solltet ihr euch mit Grafenkontraktionen beschäftigen. Hierbei geht es darum, dass ihr unwichtige Attribute entfernt und dann die Kanten verbinden könnt.
04:40
Und wir haben eine Custom-Implementierung gemacht. Und an diesem Punkt möchte ich auch gerne nochmal Laurelaine erwähnen. Sie hat diese Implementierung durchgeführt und einen Blogbeitrag geschrieben. Und auf diesem Blogbeitrag basiert auch dieser Vortrag hier. Und mit dem QR-Code könnt ihr direkt zu dem Blogbeitrag kommen.
05:02
Ich empfehle euch ihn euch anzugucken und euch mal die Implementierung anzugeschauen. Und Laurelaine und ich, wir arbeiten zusammen bei Camp2Camp. Und wir sind hier auch eben auf der Puskis mit einem Stand. Und ihr könnt gerne mal bei uns vorbeikommen.
05:20
Vielen Dank.