IEEE Copyright Notice

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice

These are the authors' versions of the work. The copyright is with ACM. They are posted here by permission of ACM for your personal use. Not for redistribution. See individual publication details for information on the publication of the definitive versions.

Springer-Verlag LNCS Copyright Notice

The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.

Work that appeared before the 1st of September 2003 was published while the authors were with the Lehrstuhl Praktische Informatik IV at the University of Mannheim.

A Long Movement Story Cut Short - On the Compression of Trajectory Data

Author(s): Markus Koegel.
Title: A Long Movement Story Cut Short - On the Compression of Trajectory Data
Published: PhD thesis, Heinrich Heine University, Düsseldorf, Germany, January 2013
Keyword(s): Vehicular Communication, Vehicular Movement, Spatio-Temporal Trajectories, Data Compression, Lossy Compression, Lossless Compression, Line Simplification, Nonlinear Approximation, Arithmetic Coding
Abstract: In mobile computing, a technology is said to be ubiquitous, if it is integrated in everyday life to such anextend that it is taken for granted instead of actually being recognized as technology. There are already numerous examples forubiquitous technologies, such as navigation systems, cell phones, or notebook computers. Many of these enable theusers to participate in mobile networks and to benefit from location-aware applications. A prominent use case ofubiquitous computing and networking is the research area of inter-vehicular communication: road vehicles areplanned to be equipped with computing units that have access to the vehicles' sensors and to wireless communicationinterfaces, so that vehicles can share information about experienced situations among each other. In doing so, thetechnique can be used to make road traffic safer, more efficient, and to provide a higher level of convenience to thepassengers. To achieve these goals, a number of efficiency and convenience applications record and transmit thevehicles' trajectories, i.e., the sequence of positions over time. However, the transmission of trajectories can induce asignificant load to the communication channel and may waste resources that are required by safety applications to workproperly. To avoid this situation, a number of lossy trajectory compression algorithms have been proposed inliterature 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 sortsof movements, we focus on the use case of vehicular trajectory compression. We take a close look at state-of-the-artsolutions that are based on geometric operations, namely line simplification and linear dead reckoning. We argue thatthough achieving good results, these models can not be the best possible approach with respect to the achievedcompression ratio, because vehicular movements are not linear. Instead, we motivate the use of nonlinear algorithms andpropose 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 canprovide 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 andtherefore merely finds a locally optimal solution. We therefore turn to an information-theoretic approach and aim atfinding an algorithm that provides the optimal compression ratio for a trajectory. We therefore use the Shannoninformation content to define the information content of a trajectory and propose a method to measure it, using amovement estimator, a discretization technique and a probability distribution. We suggest and evaluate differentcomponent implementations and find out that implementing an arithmetic coder based on this method yields significantlybetter compression ratios than the geometric approaches.We finally turn to lossless compression algorithms and consider the use of conventional byte string compressionalgorithms, such as several algorithms from the LZ family, the bzip2 algorithm and arithmetic coding. A plainapplication of these algorithms to the trajectories would not produce meaningful results, though, because subsequentlymeasured trajectory positions that are close to each other are not necessarily represented by similar byte sequencesthat would be easy to compress. We therefore propose a byte encoder that preprocesses a trajectory into a form that canbe compressed more effectively by the selected conventional compression algorithms. We evaluate the byte coder basedon the same trajectory set and see that the achieved compression ratio nearly matches the results from the lossyarithmetic 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 amaximum compression ratio can be achieved with respect to the application's accuracy requirements.
Bib entry: [XML] [BibTeX]
Download: [PDF]
Verantwortlich für den Inhalt: E-Mail sendenWE Informatik