Relationale Speicherung von Geodaten für optimierten Zugriff auf mobilen Geräten

Autor: Karsten Groll
Typ: Diplomarbeit

Abstract

TODO

Aktivitäten

Woche 1-3

Aktivitäten

  • Einarbeitung in OSM
  • Einarbeitung in Mapsforge
  • Schreiben eines Karten-Parsers für das aktuelle Kartenformat

Woche 4

Limit: 4. September

Soll

  • Rudimentäres Interface für POIs und Tiles
  • Benchmark für das Einfügen / Löschen zufälliger POIs

Aktivitäten

  • Interface überlegt
  • Debugger für das Kartenformat weitergeschrieben (Analyse ist nun theoretisch möglich.)
  • In Markus' POI-DB eingearbeitet

Probleme

  • Daten lassen sich nicht wie geplant über ein generisches Interface abrufen; Ausweg: Jede Art von Daten bekommt ihr eigenes Interface
  • Ist Verschmelzung mit Franks Routinggraph sinnvoll? Ja: Da effizient; ggf Routinggraph und Straßengraph trennen
  • Reverse Geocoding: Wäre nativ über Kacheln möglich

Woche 5

Limit: 12. September

Soll

  • Verstehen der Klasse 'MapDatabase' (Wo kann man Kacheln aus verschiedenen Quellen holen?)

Aktivitäten

  • Analysetool erstellt
  • Problem mit Libyen: Sehr viele Kacheln identischer Größe (= mit identischem Inhalt?)

Erkenntnisse / Überlegungen

  • Speicherung von Straßennamen in Kacheln
    • + Lassen sich leichter aktualisieren
    • - Problematisch für lange Straßen, da ein Straßenname in vielen Kacheln vorkommen kann.
  • Speicherung von Straßennamen straßenweise
    • - Im schlimmsten Fall #Straßen_im_Bereich Blockzugriffe nötig
    • Evaluierung notwendig: Wie viele Straßen gibt es pro Kachel
    • Kann man evtl. Basiszoomstufen für Straßen unterschiedlicher Längen definieren?
  • Anfragen auf Straßennamen
    • Kartenrenderer: Kachelweise oder anhand einer ID
    • Routing: Anhand einer Kanten- oder Knoten-ID
  • Anfragen auf POIs
    • Renderer (Overlay): Gebe mir alle POIs im Bereich (x,y)...(x',y') zurück.
  • Anfragen auf Straßengraphen
    • Renderer: Gebe für eine Kachel (einer BZS) alle Straßenverläufe und deren Typ zurück.
    • Routing: Gebe für eine Menge von Wegpunkten (Node-IDs) einen Straßenverlauf zurück. Es müssen ggf viele Blöcke ausgelesen werden; Aber: Es müssen nur die Blöcke ausgelesen werden, die auch angezeigt werden.

Mögliche Straßengraph-Kachel: Clipping + Straßennamen in Kachel
    vbeuint numberOfWayIDs # Anzahl der unterschiedlichen Wege
    foreach way do
      long wayID # Globale ID des Weges (!= OSM ID?)
      String wayName # falls in Kacheln gespeichert
      # ... (Typ, sonstige Informationen des Weges) 
      byte numberOfSegments # Anzahl der Segmente eines jeden Weges
      foreach segment do
        vbeuint deltaLat
        vbeuint deltaLon
      end
    end

  • Lohnt sich das Beseitigen der Redundanz?
  • Was ist, wenn sich das Kartenmaterial aktualisiert? Der Routinggraph müsste dann auch aktualisiert werden.
  • Caching von Rohkacheln sinnvoll?

Woche 6

Limit: 19. September

Soll

  • Finden eines geeigneten Formates zur Speicherung von Straßennamen (Lässt sich Redundanz doch vermeiden?)

Aktivitäten

Erkenntnisse

  • Interessantes Schlüsselwort: Spatial data infrastructure
  • SDTS als Austauschformat (Kachelbasiert, enthält Vektoren (Digital Line Graph Optional, DGO); nicht relevant
  • DTED - Digital Terrain Evaluation Data - Irrelevant, da nur Geländedaten beschrieben werden
  • USGS FEM - Wie SDTS - irrelevant
  • Digital Line Graph (http://eros.usgs.gov/#/Find_Data/Products_and_Data_Available/DLGs); Interessant für Straßenverläufe; Dokumentation?
  • SOSI - GML; XML-basiert frown, sad smile
  • VPF - Vector Product Format; Dokumentation lässt sich (derzeit) nicht herunterladen.
  • MapInfo TAB Format - Attribute in Datenbank; Verbindung von Daten und Rendering und Idizierung in externen Dateien - nachforschen!
  • SHP - Shapefile: geeignet für mobilen Zugriff?
  • Spatial DB for GIS: http://www.gaia-gis.it/spatialite/; Portierbarkeit auf Android?

Woche 7

Limit: 25. September

Aktivitäten

  • Nachgedacht über neues Kartenformat

Erkenntnisse

  • Format zur Speicherung von Segmenten
    Für jede Kachel: Speichere Straßeninformationen.
    Für jede Straße: Speichere Segmente
    Ein Segment ist eine Folge von lat/lon-Deltas ausgehend vom oberen linken Punkt der Kachel
    Segmente werden in der Reihenfolge ihrer Punkte gespeichert.
    Zu jedem Segment muss irgendwie das Vorgänger- / Nachfolgersegment ermittelt werden können.
      --> Für jedes Segment wird ein Bit gesetzt, welches angibt, ob das Segment am Rand der Kachel endet (also geklippt wird).
      --> Fallunterscheidung notwendig, um die Nachbarkachel zu bestimmen
      --> Alternativ: Ein Byte(!) für jedes Endsegement, welches eindeutig dessen Nachfolgekachel bestimmt
    Beispiel: (Grafik w7_segmentbeispiel)
      Kachel (1,1); Es existiert nur eine Straße 'A'
        Straßen-ID: A
      Straßenname: 'Blablubb' (Relational über die ID auffindbar machen?); Straßennamen beim ersten Lesen in Hashmap speichern, damit dieser nicht erneut gelesen werden muss.
      Segmente: 2,8
      Segment 2: Vorgänger in (1,0); Nachfolger in (2,1)
      Segment 8: Vorgänger in (1,2); Nachfolger in (1,2)

    Jedes  Segment besteht aus der Folge seiner Punkte (Einbahnstraßen lassen sich also eindeutig darstellen)
  • Straßennamen in größeren Kacheln speichern
   Sei K_s eine "Straßenkachel", welche Datenkacheln "k_0" bis "k_n" umfasst;
    foreach(k_i) do
      füge (Staßen_ID, Straßenname) in Hashmap ein
    end
    K_s := die Hashmap
  • Problem: Straßennamen kommen immernoch doppelt vor
  • Aber: Um einen Straßennamen zu ermitteln, reicht es, nur einen Straßennamen zu lesen.
  • Weiteres Problem: IDs aller Straßen müssen in allen Formaten gleich sein, damit die Zurodnung ID->Name klappt.
  • Anfragen, die damit schnell klappen sollen:
    • Liefere alle Straßenverläuge in gegebener Bounding-Box
    • Liefere Straßennamen für alle darin enthaltenen Straßen.

Woche 8

Limit: 02. Oktober

Aktivitäten

  • POIs können nun in SQLite mit R-Baumunterstützung gespeichert und ausgelesen werden
  • Einarbeitung in PBF und den MapFileWriter

Erkenntnisse

  • Kategorien über Nummern oder DML ausdrücken
  • Datenkacheln können in PBF gespeichert werden; macht agiles Entwickeln des Formates möglich

Woche 9

Limit: 09. Oktober

Aktivitäten

  • POI-Komponente abgeschlossen (Interface, Kategorien, Benchmark)

Woche 10

Limit: 16. Oktober
  • Benchmarks für Dateigrößen (Tiles als ZIP / in Datenbank mit und ohne Kompression)
  • Benchmarks für POI-Komponente (zufällige Anfragen, Einfügen, Anfragen nach Einfügen)
  • Ergebnisse:
Dateigrößen für Deutschland
    Methode              Größe
    .map                 1007 MB
    .osm.pbf              993 MB
    .zip                  843 MB
    .sqlite               1,1 GB
    .sqlite.gzip          931 MB
    best / default        860 MB
    default / default     860 MB
    best speed / default  869 MB
    best / filtered       869 MB
    default / filtered    869 MB
    best speed / filtered 869 MB 
    best / huffmann       931 MB 
    default / huffmann    923 MB 
    best speed / huffmann 931 MB 

Interessante Links

Link Beschreibung

Comments

 
Topic revision: r2 - 27 Oct 2011, KarstenGroll
 
  • Printable version of this topic (p) Printable version of this topic (p)