Article in Journal ART-2011-11

BibliographyLange, Ralph; Dürr, Frank; Rothermel, Kurt: Efficient real-time trajectory tracking.
In: The VLDB Journal. Vol. 20(5).
University of Stuttgart : Collaborative Research Center SFB 627 (Nexus: World Models for Mobile Context-Based Systems).
pp. 671-694, english.
Springer Berlin Heidelberg, October 1, 2011.
DOI: 10.1007/s00778-011-0237-7; ISSN: 1066-8888.
Article in Journal.
CR-SchemaH.2.8 (Database Applications)
Keywordsmoving objects database; MOD; trajectory tracking; dead reckoning; line simplification

Moving objects databases (MOD) manage trajectory information of vehicles, animals, and other mobile objects. A crucial problem is how to efficiently track an object's trajectory in real-time, in particular if the trajectory data is sensed at the mobile object and thus has to be communicated over a wireless network. We propose a family of tracking protocols that allow trading the communication cost and the amount of trajectory data stored at a MOD off against the spatial accuracy. With each of these protocols, the MOD manages a simplified trajectory that does not deviate by more than a certain accuracy bound from the actual movement. Moreover, the different protocols enable several trade-offs between computational costs, communication cost, and the reduction in the trajectory data: Connection-Preserving Dead Reckoning minimizes the communication cost using dead reckoning, a technique originally designed for tracking an object's current position. Generic Remote Trajectory Simplification (GRTS) further separates between tracking of the current position and simplification of the past trajectory and can be realized with different line simplification algorithms. For both protocols, we discuss how to bound the space consumption and computing time at the moving object and thereby present an effective compression technique to optimize the reduction performance of real-time line simplification in general. Our evaluations with hundreds of real GPS traces show that a realization of GRTS with a simple simplification heuristic reaches 85-90% of the best possible reduction rate, given by retrospective offline simplification. A realization with the optimal line simplification algorithm by Imai and Iri even reaches more than 97% of the best possible reduction rate.

Full text and
other links
PDF (776185 Bytes)
The original publication is available at
Copyright© Springer-Verlag 2011. This work is subject to copyright. All right are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitations, broadcastings, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German copyright Law of September 9, 1965, in its current version, and permission of use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law.
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems
Project(s)SFB-627, B5 (University of Stuttgart, Institute of Parallel and Distributed Systems, Distributed Systems)
Entry dateJune 15, 2011
   Publ. Department   Publ. Institute   Publ. Computer Science