Compressing spatio-temporal trajectories

摘要

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