Inhaltsverzeichnis |
Indexstrukturen für Geodaten
Hintergrund
Unser täglicher Umgang mit Karten bestärkt uns in der einfachen Annahme, dass es sich hierbei um 2-dimensionale Daten handelt. Und während sie oft als Latitude und Longitude gespeichert werden, so handelt es sich real doch um dreidimensionale Daten auf der Kugeloberfläche (approximativ), was korrekte Distanzberechnungen erschwert. Die Euklidische Distanz im Latitude-Longitude-Raum weist wenn sie naiv verwendet wird eine erhebliche Verzerrung auf, bei der Datumsgrenze und am Pol werden auch bei einer gewichteten Distanz die Fehler erheblich.
Flugzeuge fliegen oft entlang der Großkreise (Wikipedia:Orthodrome), so dass die Flugroute von München nach San Francisco - das südlicher als München liegt - typischerweise über Island und Grönland führt. Auf dieser Webseite können Sie sich solche Flugrouten berechnen lassen. Aber vergessen Sie dabei nicht: diese Flugroute ist in Wirklichkeit gerade, es ist nur die Projektion der Karte die sie als Bogen erscheinen lässt. Nehmen Sie einen Globus und eine Schnur um das zu überprüfen.
Thema
In dieser Arbeit sollen entsprechende Distanzfunktionen wie die "Großkreisdistanz" (Wikipedia:Orthodrome) für Indexstrukturen verwendet werden. Bei dem M-Baum und für Punktdaten ist dies in ELKI bereits möglich, für die Verwendung mit dem R-Baum und auf komplexen Objekten müssen aber erst noch zusätzliche Methoden implementiert werden.
Ein essentieller Teil der Arbeit ist auch die Evaluation der Indexstrukturen auf verschiedenen Geodaten, um sowohl die Korrektheit der Distanzfunktionen und Indexstrukturen als auch ihre Leistung zu verifizieren.
Bei Interesse können auch erweitere Strategien für bessere Indizierung untersucht werden, beispielsweise das Einfügen von Punkten in die um 360° verschobene äquivalente Position des Indexes, wenn dies zu günstigeren Seiten führt, beispielsweise bei den Aleuten, wenn man Nordamerika indiziert. Hier bietet es - vielleicht - Vorteile die Aleuten am Rande von Alaska zu speichern, statt am "Ostrand" der Weltkarte.
Aufgaben
Ziel dieser Bachelor- oder Projekt-Arbeit ist es, die bestehenden Verfahren zu vergleichen und zu testen. Hierzu soll:
- Implementierung der Distanzen für die Punkt-zu-Rechteck Abschätzung ("MinDist")
- Implementierung für komplexe Datentypen wie Rechtecke und Polygone.
- Systematische Evaluierung auf großen Geo-Datensätzen.
- Integration in der bestehenden ELKI Software.
Siehe auch
Vorkenntnisse
- Vorteilhaft sind Kenntnisse in: Java, Software-Engineering
- Vorteilhaft sind Kenntnisse über Indexstrukturen wie den R*- und M-Baum
- Vorteilhaft sind Kenntnisse in Geographie und Kartographie
Kontakt
