Trajectory Collection and Reconstruction - Mobility Data - page 29

P b (x b ,y b ,t b )

sed

P n (x n ,y n ,t n )

P' b (x b ',y b ',t b ')

P 1 (x 1 ,y 1 ,t 1 )

Figure 2.3 Using SED.

data set, (2) to ensure that the reduced data set should allow computations of
acceptable/low complexity, and (3) to ensure that a trajectory from the reduced
data set should not deviate from the original one by more than a given threshold.
From a geometric perspective, compression techniques exploit online sim-
plification algorithms that remove positions from a trajectory without warping
the trend of the trajectory or distorting the database. In general, trajectory com-
pression algorithms can be classified into four categories: top-down , bottom-up ,
sliding window ,and opening window . The top-down algorithm recursively splits
the sequence of positions and only keeps the key ( representative ) positions in
each subsequence, that is, the ones that lie far from the line that would result if
these points were removed. A classical top-down method is the Douglas-Peucker
(DP) algorithm, with many subsequent extensions. The bottom-up algorithm
starts from the finest possible representation, and merges the successive points
until some halting conditions are met. Sliding window methods compress data
in a fixed window size; open window methods use a dynamic and flexible data
segment size.
For instance, the Top-Down Time Ratio (TD-TR) and Open Window Time
Ratio (OPW-TR) algorithms have been proposed for the compression of spatio-
temporal data. The TD-TR approach uses the DP algorithm and, moreover, takes
the time into account. In particular, it replaces the Euclidean distance used in
DP by a time-aware one, called Synchronous Euclidean Distance (SED), as
illustrated in Figure 2.3 . In this example, let P b be the currently examined point
against line P 1 P n . The DP approach uses the perpendicular distance of P b to
P 1 P n , while the TD-TR uses the distance of P b to ( P ) b (i.e., the SED). The
coordinates of point P b are calculated using linear interpolation. The OPW-TR
algorithm works as follows. Initially, it defines a line segment between the first
and the third data point. If the SED from each internal point to the segment
is not greater than a given threshold, the algorithm moves the end point of the
segment one position up in the sequence. When the threshold is exceeded, the
data point that causes the threshold excess or its precedent is defined as the end
position of the current segment and the start position of a new one. As long as
new positions arrive, the method continues as described.
Two other interesting algorithms in the literature are the Thresholds and
STTrace, appropriate for online trajectory data compression. The algorithms