Dokument: A Long Movement Story Cut Short - On the Compression of Trajectory Data
| Titel: | A Long Movement Story Cut Short - On the Compression of Trajectory Data | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=23627 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20130128-180401-8 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Koegel, Markus [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Mauve, Martin [Gutachter] Dr. Scheuermann, Björn [Gutachter] | |||||||
| Stichwörter: | data compression, spatio-temporal trajectories, arithmetic coding, information theory, lossless compression | |||||||
| Dokumententyp (erweitert): | Dissertation | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibungen: | In mobile computing, a technology is said to be ubiquitous, if it is integrated in everyday life to such an
extend that it is taken for granted instead of actually being recognized as technology. There are already numerous examples for ubiquitous technologies, such as navigation systems, cell phones, or notebook computers. Many of these enable the users to participate in mobile networks and to benefit from location-aware applications. A prominent use case of ubiquitous computing and networking is the research area of inter-vehicular communication: road vehicles are planned to be equipped with computing units that have access to the vehicles' sensors and to wireless communication interfaces, so that vehicles can share information about experienced situations among each other. In doing so, the technique can be used to make road traffic safer, more efficient, and to provide a higher level of convenience to the passengers. To achieve these goals, a number of efficiency and convenience applications record and transmit the vehicles' trajectories, i.e., the sequence of positions over time. However, the transmission of trajectories can induce a significant load to the communication channel and may waste resources that are required by safety applications to work properly. To avoid this situation, a number of lossy trajectory compression algorithms have been proposed in literature that allow for an adjustable compression error bound. In this thesis, we examine compression algorithms for trajectory data. Though these algorithms are suitable for all sorts of movements, we focus on the use case of vehicular trajectory compression. We take a close look at state-of-the-art solutions that are based on geometric operations, namely line simplification and linear dead reckoning. We argue that though achieving good results, these models can not be the best possible approach with respect to the achieved compression ratio, because vehicular movements are not linear. Instead, we motivate the use of nonlinear algorithms and propose two geometric compression algorithms based on clothoid spline sketching and cubic spline interpolation, respectively. By means of an evaluation based on real-world trajectory data, we show that nonlinear algorithms can provide a better compression ratio than the optimal line simplification solution. While our spline interpolation based algorithm provides the best compression ratios, it implements a heuristic and therefore merely finds a locally optimal solution. We therefore turn to an information-theoretic approach and aim at finding an algorithm that provides the optimal compression ratio for a trajectory. We therefore use the Shannon information content to define the information content of a trajectory and propose a method to measure it, using a movement estimator, a discretization technique and a probability distribution. We suggest and evaluate different component implementations and find out that implementing an arithmetic coder based on this method yields significantly better compression ratios than the geometric approaches. We finally turn to lossless compression algorithms and consider the use of conventional byte string compression algorithms, such as several algorithms from the LZ family, the bzip2 algorithm and arithmetic coding. A plain application of these algorithms to the trajectories would not produce meaningful results, though, because subsequently measured trajectory positions that are close to each other are not necessarily represented by similar byte sequences that would be easy to compress. We therefore propose a byte encoder that preprocesses a trajectory into a form that can be compressed more effectively by the selected conventional compression algorithms. We evaluate the byte coder based on the same trajectory set and see that the achieved compression ratio nearly matches the results from the lossy arithmetic coder for the lowest selected error tolerance. With these results, we provide an answer to the question of how spatio-temporal trajectories can be compressed so that a maximum compression ratio can be achieved with respect to the application's accuracy requirements.Im Bereich der Mobilkommunikation werden Technologien als allgegenwärtig oder ubiquitär bezeichnet, wenn sie sich derart in den Alltag integrierten, dass sie nicht mehr als Technologien wahrgenommen werden, wie zum Beispiel Navigationssysteme, Mobiltelefone oder Notebooks. Viele dieser Technologien sind vernetzt und bieten ihren Benutzern ortsbezogene Dienste an. Ein prominenter Anwendungsfall hierfür ist die Fahrzeug-zu-Fahrzeug Kommunikation, die derzeit noch erforscht und prototypisch entwickelt wird. Hierbei werden reguläre Straßenfahrzeuge mit Computern ausgestattet, die Zugriff zu den Fahrzeugsensoren und Funkkommunikationsmodulen haben und somit Informationen aus vergangenen Situationen untereinander austauschen und verbreiten können; so sollen die Sicherheit, die Effizienz und der Komfort im Straßenverkehr gesteigert werden. Hierfür zeichnen eine Reihe von Effizienz- und Komfortanwendungen Zeit- und Bewegungsdaten (Trajektorien) auf und übertragen diese zur Weiterverarbeitung an externe Server oder Netzwerke. Da solche Trajektorien jedoch potentiell sehr groß werden, können deren Übertragungen eine erhebliche Datenlast auf dem drahtlosen Medium verursachen. Dadurch entsteht die Gefahr, dass Ressourcen belegt werden, die von Sicherheitsanwendungen dringend benötigt werden. Um solche Situationen zu vermeiden, wurden bereits verlustbehaftete Trajektoriekompressionsmethoden in der Literatur vorgeschlagen, bei denen eine harte räumliche Fehlerschranke frei einstellbar ist. In dieser Arbeit untersuchen wir Kompressionsalgorithmen für Trajektorien. Auch wenn diese Algorithmen für beliebige Bewegungen geeignet sind, konzentrieren wir uns dabei auf Fahrzeugbewegungen. Wir betrachten den derzeitigen Stand der Technik, bei dem geometrische Operationen, nämlich Linienvereinfachung und lineare Bewegungsmodelle verwendet werden. Wir argumentieren, dass diese Modelle nicht die bestmögliche Kompression erreichen können, da Fahrzeugbewegungen nicht linear sind und bekräftigen stattdessen die Verwendung von nichtlinearen Modellen. Wir schlagen zwei geometrische Kompressionsalgorithmen vor, die auf Klothoidensplines, bzw. kubischer Splineinterpolation basieren. Unsere Auswertungen auf Basis von Realweltdaten zeigen, dass nichtlineare Algorithmen eine bessere Kompressionsrate erzielen können als die optimalen Linien vereinfachenden Ansätze. Während unser auf Splineinterpolation basierender Algorithmus die beste Kompressionsrate für geometrische Verfahren erreicht, arbeitet dieser heuristisch und findet lediglich eine lokal optimale Lösung. Wir verwenden daher einen informationstheoretischen Ansatz, um einen Algorithmus zu finden, der eine bestmögliche Kompressionsrate erreicht. Mithilfe des Shannon-Informationsgehalts definieren wir den Informationsgehalt einer Trajektorie und schlagen eine Methode vor, um diesen zu messen. Hierbei findet ein Bewegungsschätzer, eine Diskretisierung von Schätzfehlern und eine Wahrscheinlichkeitsverteilung Anwendung. Wir beschreiben verschiedene Implementierungsalternativen für diese Komponenten und zeigen in unserer Auswertung, dass die Umsetzung dieser Methode in einem arithmetischen Kodierer deutlich bessere Kompressionsraten als die geometrischen Ansätze erzielt. Als Abschluss wenden wir uns den konventionellen verlustfreien Kompressionsalgorithmen zu und untersuchen mehrere Algorithmen aus der LZ-Familie, den bzip2-Algorithmus und die arithmetische Kodierung. Eine einfache Anwendung dieser Algorithmen auf die Trajektorien ist allerdings nicht sinnvoll, weil sich die Binärrepräsentationen ähnlicher Trajektoriepositionen nicht zwangsläufig ähneln und somit nicht notwendigerweise gut zu komprimieren wären. Wir präsentieren daher einen Byte-Kodierer, der in einem Vorverarbeitungsschritt den Bytecode einer Trajektorie derart umformatiert, dass er besser durch die ausgewählten konventionellen Algorithmen komprimiert werden kann. Unsere Auswertung zeigt, dass die erreichte Kompressionsrate der verlustfreien Algorithmen beinahe der des verlustbehafteten arithmetischen Kodierers für die niedrigste untersuchte Fehlertoleranz entspricht. Durch unsere Ergebnisse zeigen wir, wie eine Trajektorie komprimiert werden muss, um eine möglichst hohe Kompressionsrate in Abhängigkeit von den Genauigkeitsanforderungen der jeweiligen Anwendung zu erreichen. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Bezug: | 2013 | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Rechnernetze | |||||||
| Dokument erstellt am: | 28.01.2013 | |||||||
| Dateien geändert am: | 28.01.2013 | |||||||
| Promotionsantrag am: | 12.12.2012 | |||||||
| Datum der Promotion: | 25.01.2013 |
