Bachelor Thesis BCLR-0114

BibliographyBagg, 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-SchemaG.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 dateJune 23, 2014
   Publ. Computer Science