Externe komprimierte Graphdarstellungen

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.