Diploma Thesis DIP-2847

BibliographyReimann, Steffen: Preprocessing von Positionsdaten mit Algorithmen zur Polygonzugvereinfachung.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2847 (2009).
113 pages, german.
CR-SchemaH.2.8 (Database Applications)
C.2.4 (Distributed Systems)
F.2.2 (Nonnumerical Algorithms and Problems)
G.1.2 (Numerical Analysis Approximation)
KeywordsPolygonzugvereinfachung; semantische Kompression
Abstract

Mobile Objekte, die mit Positionssensoren ausgerüstet sind, liefern kontinuierliche Positionsdatenströme. Dabei entstehen große Datenmengen, die entweder direkt verarbeitet oder für die spätere Auswertung gespeichert werden. Um den Verarbeitungsaufwand zu reduzieren und Speicherplatz zu sparen ist es notwendig, die Positionsdatenströme zu komprimieren. Dadurch sollen redundante Daten herausgefiltert und die Datenmenge insgesamt verkleinert werden.

Von Kaya wurde in einer vorausgehenden Arbeit gezeigt, dass sich Positionsdatenströme effizient komprimieren lassen. Auf diesen Ergebnissen aufbauend zeigt diese Arbeit, wie Positionsdatenströme mithilfe von Algorithmen zur Polygonzugvereinfachung komprimiert werden können, ohne eine vorgegebene Abweichung gegenüber dem ursprünglichen Datenstrom zu überschreiten. Dazu werden verschiedene Algorithmen zur Polygonzugvereinfachung untersucht und mit den Algorithmen von Kaya verglichen.

Außerdem wird ein Verfahren vorgestellt, das den Positionsdatenstrom mithilfe einer digitalen Straßenkarte komprimiert. Dazu müssen die Positionen mit der Straßenkarte abgeglichen und zusammengefasst werden.

Untersucht wurde in beiden Fällen insbesondere die Datenreduktion und die experimentelle Laufzeit der Algorithmen. Dazu wurden Simulationen auf echten Positionsdaten durchgeführt. Die Simulationsdaten stammen aus dem Infati-Projekt von Prof. Jensen u. a. von der Universität Aalborg (Dänemark).

Die Simulationsergebnisse zeigen, dass Algorithmen zur Polygonzugvereinfachung die verwendeten echten Positionsdatenströme um bis zu 97 Prozent komprimieren können, ohne dabei mehr als 50 Meter von den ursprünglichen Datenströmen abzuweichen.

Interessanterweise unterscheidet sich die experimentelle Laufzeit der Algorithmen trotz gleicher Kompressionsrate um mehrere Größenordnungen. Das hat erhebliche Auswirkungen auf die praktische Nutzbarkeit der Verfahren.

Das kartenbasierte Verfahren erreicht im Vergleich mit den Verfahren zur Polygonzugvereinfachung eine niedrigere Kompressionsrate, die hauptsächlich vom Aufbau der Straßenkarte abhängt.

Full text and
other links
PDF (1152524 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
ContactSenden Sie eine E-Mail an diplomarbeit@steffen-reimann.de
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Applications of Parallel and Distributed Systems
Superviser(s)Hönle, Nicola
Project(s)Nexus SFB 627 - B5
Entry dateMarch 7, 2010
   Publ. Computer Science