Compressing spatio-temporal trajectories

TY - JOUR

T1 - Compressing spatio-temporal trajectories

AU - Gudmundsson, Joachim

AU - Katajainen, Jyrki

AU - Merrick, Damian

AU - Ong, Cahya

AU - Wolle, Thomas

PY - 2009

Y1 - 2009

N2 - 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(nlogkn) for k=2 or k=3 depending on the type of simplification.

AB - 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(nlogkn) for k=2 or k=3 depending on the type of simplification.

U2 - 10.1016/j.comgeo.2009.02.002

DO - 10.1016/j.comgeo.2009.02.002

M3 - Journal article

SN - 0925-7721

VL - 42

SP - 825

EP - 841

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 9

ER -