Compressing spatio-temporal trajectories
Authors:Joachim Gudmundsson, Jyrki Katajainen, Damian Merrick, Cahya Ong, and Thomas Wolle
Published in:Computational Geometry—Theory and Applications 42,9 (2009), 825-841
Full text:<pdf.gif>PDF (646 kB)  
Copyright:© Elsevier B.V.

A trajectory is a sequence of locations, each associated with a timestamp, describing the movement of a point. Trajectory data is becoming increasingly available and the size of recorded trajectories is getting larger. In this paper we study the problem of compressing planar trajectories such that the most common spatio-temporal queries can still be answered approximately after the compression has taken place. In the process, we develop an implementation of the Douglas-Peucker path-simplification algorithm which works efficiently even in the case where the polygonal path given as input is allowed to self-intersect. For a polygonal path of size n, the processing time is O(n logk n) for k = 2 or k = 3 depending on the type of simplification.

Related:<html.gif>HTML (Conference paper)  
  author = {Joachim Gudmundsson and Jyrki Katajainen and Damian Merrick and
    Cahya Ong and Thomas Wolle},
  title = {Compressing spatio-temporal trajectories},
  journaltitle = {Computational Geometry---Theory and Applications},
  volume = {42},
  number = {9},
  year = {2009},
  pages = {825--841},
This page was generated by Jyrki Katajainen <> on 31.12.2011.