Bibliography | Bagg, Tobias: Externe komprimierte Graphdarstellungen. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 114 (2014). 52 pages, german.
|
CR-Schema | G.2.2 (Discrete Mathematics Graph Theory) E.4 (Data Coding and Information Theory)
|
Abstract | In dieser Bachelorarbeit wird untersucht, inwiefern sich Graphdaten für Routenplaner komprimieren lassen und gleichzeitig kürzeste Wege effizient berechnet werden können. Motiviert wird dies insbesondere durch die weiterhin wachsende Größe des Kartenmaterials, was aus dem ständig verbesserten Detailgrad resultiert, als auch durch die Vergrößerung der geographischen Ausdehnung dieser Graphen. Erschwerend kommt hinzu, dass Speicher auf Geräten, welche häufig zur Routenplanung eingesetzt werden, auch heutzutage noch eine eingeschränkte Ressource darstellt. Ebenfalls sind Prozessoren in diesem Einsatzbereich eher auf Energieeffizienz ausgelegt und deshalb leistungsschwächer. Diese Arbeit soll erläutern, wie sich diese Herausforderungen durch die richtige Wahl von Algorithmen, Datenstrukturen und Techniken bewältigen lassen. Die gewählten Algorithmen und Datenstrukturen wurden in Java implementiert. Die Implementierung wurde mit unterschiedlichen Parametern für Kompression und dem Verhalten des Caching evaluiert, sowie interpretiert und in dieser Arbeit festgehalten.
|
Full text and other links | PDF (1426010 Bytes)
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
Superviser(s) | Funke, Stefan |
Entry date | June 23, 2014 |
---|