Effiziente Datenanalyse in Netzwerkgraphen: Durch User Defined Functions in PostgreSQL

1 - Effiziente Datenanalyse in Netzwerkgraphen:Durch User Defined Functions in PostgreSQL [Seite 1]
1.1 - Einleitung [Seite 3]
1.2 - Abstract [Seite 4]
1.3 - Inhaltsverzeichnis [Seite 5]
1.4 - Abbildungsverzeichnis [Seite 7]
1.5 - Tabellenverzeichnis [Seite 8]
1.6 - Verzeichnis der Listings [Seite 9]
1.7 - 1. Einleitung [Seite 11]
1.7.1 - 1.1. Aufbau der Arbeit [Seite 11]
1.7.2 - 1.2. Beschreibung des Mesh-Netzwerks als Graph [Seite 12]
1.7.3 - 1.3. Qualität der zu analysierenden Daten [Seite 13]
1.7.4 - 1.4. Ziel der Arbeit [Seite 17]
1.7.5 - 1.5. Vorausgesetzte Hard- und Software [Seite 20]
1.8 - 2. Stand der Technik [Seite 22]
1.8.1 - 2.1. Routing-Algorithmen [Seite 22]
1.8.2 - 2.2. Metriken [Seite 23]
1.8.3 - 2.3. Betrachtung der bestehenden Implementierung als Cloud-Service [Seite 24]
1.8.3.1 - 2.3.1. Algorithmische Komplexit¨at [Seite 25]
1.8.3.2 - 2.3.2. Vor- und Nachteile der Cloudl¨osung [Seite 29]
1.9 - 3. Vorbetrachtungen einer hochperformanten Lösung [Seite 31]
1.9.1 - 3.1. Wahl des DBMS und der Programmiersprache [Seite 31]
1.9.1.1 - 3.1.1. Wahl des Datenbankmodells [Seite 31]
1.9.1.2 - 3.1.2. Wahl des DBMS [Seite 36]
1.9.1.3 - 3.1.3. Wahl der Programmiersprache [Seite 38]
1.9.2 - 3.2. Schnittstellendefinition [Seite 42]
1.9.3 - 3.3. Möglichkeiten der Performancemessung [Seite 46]
1.10 - 4. Optimierungen in der Implementierung [Seite 50]
1.10.1 - 4.1. Algorithmische Optimierungen [Seite 50]
1.10.1.1 - 4.1.1. Optimierung des Dijkstra-Algorithmus [Seite 50]
1.10.1.2 - 4.1.2. Optimierung des Graphen [Seite 52]
1.10.1.3 - 4.1.3. Die"General-Gateway-Strategie" [Seite 53]
1.10.1.4 - 4.1.4. Nutzung stabiler Teilergebnisse bei ähnlichen Graphen [Seite 56]
1.10.2 - 4.2. Performanceoptimierter Programmierstil [Seite 61]
1.10.2.1 - 4.2.1. Quellcodedesign [Seite 61]
1.10.2.2 - 4.2.2. Zusammenhang zur algorithmischen Komplexität [Seite 63]
1.10.2.3 - 4.2.3. Design Pattern [Seite 64]
1.10.2.4 - 4.2.4. Implementierung von"unendlich" [Seite 65]
1.10.2.5 - 4.2.5. Adjazenzmatrix statt Adjazenzliste [Seite 66]
1.10.3 - 4.3. Parallelisierung [Seite 67]
1.10.3.1 - 4.3.1. Multithreaded Dijkstra [Seite 67]
1.10.3.2 - 4.3.2. Dijkstra auf der GPU [Seite 73]
1.10.4 - 4.4. Zusammenfassung und Ergebnisse [Seite 75]
1.11 - 5. Testläufe - Beispiele für Datenabfragen [Seite 78]
1.11.1 - 5.1. Alle Routen zu allen Zeitpunkten [Seite 80]
1.11.2 - 5.2. Routenänderungen zwischen zwei Zeitpunkten [Seite 81]
1.11.3 - 5.3. Routenänderungen bei Ausfall eines Knotens [Seite 83]
1.11.4 - 5.4. Routenänderungen bei Ausfall zweier Knoten [Seite 86]
1.11.5 - 5.5. Knoten die häufig auf Routen liegen [Seite 89]
1.11.6 - 5.6. Wichtige Knoten und Kanten [Seite 92]
1.11.7 - 5.7. Routenänderungen bei Ausfall einer Kante [Seite 94]
1.11.8 - 5.8. Suche nach Flaschenhälsen [Seite 97]
1.12 - 6. Zusammenfassung und Ausblick [Seite 100]
1.12.1 - 6.1. Zusammenfassung [Seite 100]
1.12.2 - 6.2. Ausblick [Seite 101]
1.13 - Literaturverzeichnis [Seite 104]
1.14 - A. Anhang: SQL Anfragen [Seite 107]
1.14.1 - A.1. Anzahl neuer Datensätze pro Minute [Seite 107]
1.14.2 - A.2. Prüfung der Vollständigkeit der Daten [Seite 108]
1.14.3 - A.3. Prüfung der Korrektheit der Daten [Seite 110]
1.14.4 - A.4. Maximale Knotenanzahl auf kürzesten Pfaden [Seite 111]
1.14.5 - A.5. Floyd-Warshall-Berechnung in SQL [Seite 113]
1.14.6 - A.6. Floyd-Warshall-Berechnung mit PL/Python [Seite 114]
1.14.7 - A.7. Test der General-Gateway-Strategie [Seite 115]
1.14.8 - A.8. Implementierung der Algebra aus Abschnitt 4.1.4 [Seite 116]
1.15 - B. Anhang: Suche nach einerPartitionierung [Seite 117]