One-Pass Error Bounded Trajectory Simplification
Xuelian Lin

Shuai Ma∗

Han Zhang

Tianyu Wo

Jinpeng Huai

SKLSDE Lab, Beihang University, Beijing, China
Beijing Advanced Innovation Center for Big Data and Brain Computing, Beijing, China

arXiv:1702.05597v1 [cs.DB] 18 Feb 2017

{linxl,

mashuai, zhanghan, woty, huaijp}@buaa.edu.cn

ABSTRACT
Nowadays, various sensors are collecting, storing and transmitting tremendous trajectory data, and it is known that
raw trajectory data seriously wastes the storage, network
band and computing resource. Line simplification (LS) algorithms are an effective approach to attacking this issue by
compressing data points in a trajectory to a set of continuous line segments, and are commonly used in practice. However, existing LS algorithms are not sufficient for the needs
of sensors in mobile devices. In this study, we first develop a
one-pass error bounded trajectory simplification algorithm
(OPERB), which scans each data point in a trajectory once
and only once. We then propose an aggressive one-pass error bounded trajectory simplification algorithm (OPERB-A),
which allows interpolating new data points into a trajectory
under certain conditions. Finally, we experimentally verify
that our approaches (OPERB and OPERB-A) are both efficient and effective, using four real-life trajectory datasets.

1.

INTRODUCTION

Various mobile devices, such as smart-phones, on-board
diagnostics, and wearable smart devices, have been widely
using their sensors to collect massive trajectory data of moving objects at a certain sampling rate (e.g., 5 seconds),
and transmit it to cloud servers for location based services, trajectory mining and many other applications. It
is known that transmitting and storing raw trajectory data
consumes too much network bandwidth and storage capacity
[2–4,10–13,15,18–22]. Further, we find that the online transmitting of raw trajectories also seriously aggravates several
other issues such as out-of-order and duplicate data points
in our experiences when implementing an online vehicleto-cloud data transmission system. Fortunately, these issues can be resolved or greatly alleviated by the trajectory
compression techniques [2–4, 6, 8, 11–13, 15, 18, 19, 21, 23, 24],
among which line simplification based methods are widely
used [2–4, 6, 8, 11, 12, 18, 23], due to their distinct advantages: (a) simple and easy to implement, (b) no need of

This work is licensed under the Creative Commons AttributionNonCommercial-NoDerivatives 4.0 International License. To view a copy
of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For
any use beyond those covered by this license, obtain permission by emailing
info@vldb.org.
Proceedings of the VLDB Endowment, Vol. 10, No. 7
Copyright 2017 VLDB Endowment 2150-8097/17/03.

...

Figure 1: A trajectory T [P0 , . . . , P14 ] with fifteen points
is represented by four continuous line segments (solid
blue), compressed by the Douglas–Peucker algorithm [6].

extra knowledge and suitable for freely moving objects [20],
and (c) bounded errors with good compression ratios. Line
simplification algorithms belong to lossy compression, and
use a set of continuous line segments to represent a compressed trajectory, as shown in Figure 1.
The most notable line simplification (LS) algorithm is the
Douglas-Peucker algorithm [6] invented in 1970s, for reducing the number of points required to represent a digitized
line or its caricature in the context of computer graphics
and image processing. The basic Douglas-Peucker algorithm
(DP) is a batch method with a time complexity of O(n2 ),
where n is the number of data points in a given trajectory
to be compressed. Its batch nature and high time complexity make it not suitable for the online scenarios. Several
LS algorithms have been developed based on DP, e.g., by
combining DP with sliding/open windows [11, 15] for online
processing. However, these methods still have a high time
and/or space complexity, which significantly hinders their
utility in resource-constrained mobile devices [12].
Recently, BQS [12] has been proposed, using a new distance checking method by picking out at most eight special
points from an open window based on a convex hull, e.g., a
rectangular bounding box with two bounding lines, so that
when a new point is added to a window, it only needs to
calculate the distances of the special points to a line, instead of all data points in the window, in many cases. The
time complexity of BQS remains O(n2 ) in the worst case,
as BQS falls back to DP when the eight special points cannot be used. However, its simplified version, FBQS directly
outputs a line segment, and starts a new window when the
eight special points cannot bound all the points considered
so far. Indeed, FBQS has a linear time complexity, and is
the fastest LS based solution for trajectory compression.
An LS algorithm is one-pass if it processes each point in
a trajectory once and only once when compressing the trajectory. Obviously, one-pass algorithms have low time and
space complexities, and are more appropriate for online processing. Unfortunately, existing algorithms such as DP, BQS

and FBQS are not one-pass, as data points in a trajectory
are processed multiple times in these algorithms. Indeed, it
remains open whether there exist one-pass error bounded LS
based effective trajectory compression algorithms.
Contributions & Roadmap. To this end, we propose two
one-pass error bounded LS based algorithms for compressing
trajectories in an efficient and effective way.
(1) We first develop a one-pass error bounded trajectory simplification algorithm (OPERB, Section 4) that runs in O(n)
time and O(1) space. OPERB is based on a novel local distance checking method, and equipped with five optimization
techniques to further improve its compression ratio.
(2) We then propose an aggressive one-pass error bounded
trajectory simplification algorithm (OPERB-A, Section 5)
that remains in O(n) time and O(1) space. OPERB-A allows
interpolating new data points into a trajectory under certain
conditions and with practical considerations. The rational
lies in that moving objects have sudden track changes while
data points may not be sampled due to various reasons.
(3) Using four real-life trajectory datasets (Taxi, Truck,
SerCar, GeoLife), we finally conduct an extensive experimental study (Section 6), by comparing our algorithms OPERB
and OPERB-A with FBQS (the fastest existing LS algorithm)
and DP (the best existing LS algorithm in terms of compression ratio). We find that OPERB and OPERB-A are on
average (4.1, 4.1, 5.4, 5.2) times faster than FBQS on (Taxi,
Truck, SerCar, GeoLife), respectively. For compression ratios, OPERB is comparable with DP, and OPERB-A is better
than DP that is on average (84.2%, 86.4%, 97.1%, 94.7%) of
DP on (Taxi, Truck, SerCar, GeoLife), respectively.
An extended version and some used datasets are at [1].

2.

RELATED WORK

Trajectory compression algorithms are normally classified into two categories, namely lossless compression and
lossy compression [18]. (1) Lossless compression methods
enable exact reconstruction of the original data from the
compressed data without information loss. For example,
delta compression [19] is a lossless compression technique,
which has zero error and a time complexity of O(n), where
n is the number of data points in a trajectory. The limitation of lossless compression lies in that its compression
ratio is relatively poor [19]. (2) In contrast, lossy compression methods allow errors or derivations, compared with the
original trajectories. These techniques typically identify important data points, and remove statistical redundant data
points from a trajectory, or replace original data points in a
trajectory with other places of interests, such as roads and
shops. They focus on good compression ratios with acceptable errors, and a large number of lossy trajectory compression techniques have been developed. In this work we focus
on lossy compression of trajectory data,
We next introduce the related work on lossy trajectory
compression from two aspects: line simplification based
methods and semantics based methods.
Line simplification based methods. Line simplification
based methods not only have good compression ratios and
deterministic error bounds, but also are easy to implement
(see an evaluation report [23])). Hence, they are widely used
in practice, even for freely moving objects without the restriction of road networks. And according to the way they

process trajectories, they are further divided into batch processing and online processing methods [19].
(1) Batch algorithms require that all trajectory points must
be loaded before they start compressing. Batch algorithms
can be either top-down or bottom-up. Top-down algorithms
recursively divide a trajectory into sub-trajectories until the
stopping condition is met [11]. The DP algorithm [6] is
the most classic top-down approach, and [15] improves DP
with the synchronous Euclidean distance, instead of the Euclidean distance. Bottom-up algorithms [3,11] are the natural complement to top-down ones, which recursively merge
adjacent sub-trajectories with the smallest distance, initially
n/2 sub-trajectories for a trajectory with n points, until the
stopping condition is met. Note that the distances of newly
generated line segments are recalculated during the process.
(2) Online algorithms do not need to have the entire trajectory ready before they start compressing, and are appropriate for compressing trajectories on sensors of mobile devices.
Existing online algorithms [11, 15, 18] usually use a fixed or
open window and compress sub-trajectories in the window.
However, these existing online algorithms are not onepass. In this study, we propose a novel local distance checking method, based on which we develop one-pass online algorithms that are totally different from the window based
algorithms. Further, as shown in the experimental study,
our approaches are clearly superior to the existing online
algorithms, in terms of both efficiency and effectiveness.
Semantics based methods. The trajectories of certain
moving objects such as cars and trucks are constrained by
road networks. These moving objects typically travel along
road networks, instead of the line segment between two
points. Trajectory compression methods based on road networks [4, 5, 7, 9, 20, 24] project trajectory points onto roads
(also known as Map-Matching). Moreover, [7,24] mines and
uses high frequency patterns of compressed trajectories, instead of roads, to further improve compression effectiveness.
Some methods [21, 22] compress trajectories beyond the use
of road networks, which further make use of other user specified domain knowledge, such as places of interests along the
trajectories [21]. There are also compression algorithms preserving the direction of the trajectory [13, 14].
These approaches are orthogonal to line simplification
based methods, and may be combined with each other to
further improve the effectiveness of trajectory compression.

3.

PRELIMINARIES

In this section, we introduce some basic concepts and existing algorithms for trajectory simplification.

3.1

Basic Notations

Points (P ). A data point is defined as a triple P (x, y, t),
which represents that a moving object is located at longitude
x and latitude y at time t. Note that data points can be
viewed as points in a three-dimension Euclidean space.
...
...
Trajectories (T ). A trajectory T [P0 , . . . , Pn ] is a sequence
of data points in a monotonically increasing order of their associated time values (i.e., Pi .t < Pj .t for any 0 ≤ i < j ≤ n).
Intuitively, a trajectory is the path (or track) that a moving
object follows through space as a function of time [16].
Directed line segments (L). A directed line segment
# »
(or line segment for simplicity) L is defined as Ps Pe , which

...
Algorithm DP(T [P0 , . . . , Pn ], ζ)
...
1. for each point Pi (i ∈ [0, n]) in T [P0 , . . . , Pn ] do
2.
compute d(Pi , L) between Pi and L(P0 , Pn );
3. let d(Pk , L) := max{d(P0 , L), . . . , d(Pn , L)};
4. if d(Pk , L) ≤ ζ then
5.
return {L(P0 , Pn )}.
6. else
...
...
7.
return DP(T [P0 , . . . , Pk ], ζ) ∪ DP(T [Pk , . . . , Pn ], ζ).

Figure 2: Example included angles and distances.
represents the closed line segment that connects the start
point Ps and the end point Pe . Note
... that here Ps or Pe may
not be a point in a trajectory T , and hence, we also use
...
notation R instead of L when both Ps and Pe belong to T .
We also use |L| and L.θ ∈ [0, 2π) to denote the length of a
directed line segment L, and its angle with the x-axis of the
coordinate system (x, y), where x and y are the longitude
and latitude, respectively. That is, a directed line segment
# »
L = Ps Pe can be treated as a triple (Ps , |L|, L.θ).
Piecewise line representation
(T ). A piece-wise line
...
representation of a trajectory T [P0 , . . . , Pn ] is T [L0 , . . . , Lm ]
(0 < m ≤ n), a sequence of continuous directed line seg...
#
»
ments Li = Psi Pei of T (i ∈ [0, m]) such that L0 .Ps0 = P0 ,
Lm .Pem = Pn and Li .Pei = Li+1 .Psi+1 for all i ∈ [0, m − 1].
repreNote that each directed line segment in T essentially
...
sents a continuous sequence of data points in T .
Included angles (∠). Given two directed line segments
#
»
#
»
L1 = Ps Pe1 and L2 = Ps Pe2 with the same start point Ps ,
the included angle from L1 to L2 , denoted as ∠(L1 , L2 ), is
L2 .θ − L1 .θ. For convenience, we also represent the included
angle ∠(L1 , L2 ) as ∠Pe1 Ps Pe2 .
Distances (d). Given a point Pi and a directed line seg# »
ment L = Ps Pe , the distance of Pi to L, denoted as d(Pi , L),
is the Euclidean distance from Pi to the line Ps Pe , commonly
adopted by most existing LS methods, e.g., [3, 6, 8, 11, 12].
Example 1: (1) In Figure 1, the four continuous directed
# » # » #
» #
»
line segments P0 P5 , P5 P8 , P8 P10...
, P10 P14 form a piecewise
line representation of trajectory T [P0 , . . . , P14 ].
(2) Figure 2 shows two different cases of included angles. In
# »
each case, there are two directed line segments L1 = P0 P1
# »
and L2 = P0 P2 with the same start point P0 . The included
angle ∠(L1 , L2 ) from L1 to L2 lies in (−2π, 2π), and is −19π
12
and 3π
in Figures 2(1)&(2), respectively.
4
(3) The distance d(P2 , L1 ) is illustrated in Figures 2 as dotted green line segments.
2

3.2

Line Simplification Algorithms

Line simplification (LS) algorithms are a type of important
and widely adopted trajectory compression methods, and we
next briefly introduce these algorithms.
Basic Douglas-Peucker algorithm. We first introduce
the Basic Douglas-Peucker (DP) algorithm [6] shown in Figure 3, the foundation of
... many subsequent LS algorithms.
Given a trajectory T [P0 , . . . , Pn ] and an error bound ζ,
algorithm
... DP uses the first point P0 and the last point
Pn of T as the start point Ps and the end point Pe of
the first line segment L(P0 , Pn ), then it calculates the distance d(Pi , L) for each point Pi (i ∈ [0, n]) (lines 1–2). If
d(Pk , L) = max{d(P0 , L), . . . , d(Pn , L)} ≤ ζ, then...it returns
{L(P0 , Pn )} (lines 3–5). Otherwise, it divides T into two

Figure 3: Basic Douglas-Peucker algorithm
...
...
sub-trajectories T [P0 , . . . , Pk ] and T [Pk , . . . , Pn ], and recursively compresses these sub-trajectories until the entire trajectory has been considered (lines 6–7).
The DP algorithm is clearly a batch algorithm, as the
entire trajectory is needed at the beginning [15], and its time
complexity is O(n2 ). Moreover, [8] developed an improved
method with a time complexity of O(n log n).
...
Example 2: Consider the trajectory T [P0 , . . . , P14 ] shown
#
»
in Figure 1. Algorithm DP firstly creates P0 P14 , then it cal#
»
culates the distance of each point in {P0 , . . . , P14 } to P0 P14 .
#
»
It finds that P10 has the maximum distance to P0 P14 , which
is greater than ζ. Then it goes to compress sub-trajectories
[P0 , . . . , P10 ] and [P10 , . . . , P14 ], separately. Similarly, subtrajectory [P0 , . . . , P10 ] is split to [P0 , . . ., P5 ] and [P5 , . . .,
P10 ], and [P5 , . . ., P10 ] is split to [P5 , . . . , P8 ] and [P8 , P9 ,
P10 ]. Finally, algorithm DP outputs four continuous directed
# » # » #
» #
»
line segments {P0 P5 , P5 P8 , P8 P10...
, P10 P14 }, i.e., a piece-wise
line representation of trajectory T [P0 , . . . , P14 ]
2
Online algorithms. We next introduce two classes of DP
based online algorithms that make use of sliding windows to
speed up the compressing
efficiency [11, 12, 15].
...
Given a trajectory T [P0 , . . . , Pn ] and an error bound ζ, algorithm OPW [15] maintains a window W [Ps , . . . , Pk ], where
Ps and Pk are the start and end points, respectively. Initially, Ps = P0 and Pk = P1 , and the window W is gradually
expanded by adding new points one by one. OPW tries to
compress all points in W [Ps , . . . , Pk ] to a single line segment L(Ps , Pk ). If the distances d(Pi , L) ≤ ζ for all points
Pi (i ∈ [s, k]), it simply expands W to [Ps , . . . , Pk , Pk+1 ]
(k + 1 ≤ n) by adding a new point Pk+1 . Otherwise, it produces a new line segment L(Ps , Pk−1 ), and replaces W with
a new window [Pk−1
... , . . . , Pk+1 ]. The above process repeats
until all points in T have been considered. Algorithm OPW
is not efficient enough for compressing long trajectories as
it remains in O(n2 ) time, the same as the DP algorithm.
BQS [12] reduces the compression time by introducing a
convex hull that bounds a certain number of points. For a
buffered sub trajectory [Ps , . . . , Pk ], it splits the space into
four quadrants. For each quadrant, a rectangular bounding
box is firstly created using the least and highest x values
and the least and highest y values among points Ps , . . . , Pk .
Then another two bounding lines connecting points Ps and
Ph and points Ps and Pl are created such that lines Ps Ph and
Ps Pl have the largest and smallest angles with the x-axis,
respectively. Here Ph , Pl ∈ {Ps , . . . , Pk }. The bounding box
and the two lines together form a convex hull. BQS picks
out at most eight significant points in a quadrant. In many
cases, (1) it only calculates the distances of the significant
points to line Ps Pk ; otherwise, (2) it needs to compute all
distances d(Pi , L(Ps , Pk )) (i ∈ [s, k]) as DP. BQS remains in
O(n2 ) time. However, its simplified version FBQS essentially
avoids case (2) to achieve an O(n) time complexity.

Figure 4: Examples for algorithm BQS.

Figure 5: An example of the fitting function

Example 3: In Figure 4, the bounding box c1 c2 c3 c4 and the
two lines Ps Ph = P0 P1 and Ps Pl = P0 P2 form a convex hull
u1 u2 c2 l2 l1 c4 . BQS computes the distances of u1 , u2 , c2 , l2 , l1
and c4 to line P0 P6 when k = 6 or to line P0 P7 when k = 7.
When k = 6, all these distances to P0 P6 are less than ζ,
hence BQS goes on to the next point (case 1); When k = 7,
the max and min distances to P0 P7 are larger and less than
ζ, respectively, and BQS needs to compress sub-trajectory
[P0 , . . . , P7 ] along the same line as DP (case 2).
2
...
Error bounded algorithms. Given a trajectory T and
its compression
algorithm A that produces another trajec...
tory T 0 , we say that algorithm A is error bounded...by ζ if
...
for each point P in T , there exists a point Pj in T 0 with
d(P, L(Pj , Pj+1 )) ≤ ζ. Note that all the above LS algorithms are error bounded by ζ, a parameter typically set by
experts based on the need and analysis of applications.

Fitting function
F. Given an error bound ζ and a sub...
trajectory Ts [Ps , . . . , Ps+k ], F is as follows.

4.

ONE-PASS SIMPLIFICATION

In this section, we first develop a local distance checking approach that is the key for one-pass trajectory simplification algorithms. We then present a One-Pass ERror
Bounded trajectory simplification algorithm, referred to as
OPERB. Finally, we propose five optimization techniques.

4.1

Local Distance Checking

Existing trajectory simplification algorithms (e.g., DP [6]
and online algorithms [11,12,15]) essentially employ a global
distance checking approach to assuring error bounds, although online algorithms restrict the checking within a window. That is to say, whenever a new directed line seg#
»
ment Ri = Ps Ps+i (i ∈ [1, k]) is formed for a sub-trajectory
...
Ts [Ps , . . . , Ps+k ], these algorithms always check its distances
to all or a subset of data points {Ps , . . . , Ps+i } to Ri , and,
therefore, a data point is checked multiple times, depending
on its order in the trajectory and the number of directed
line segments formed. Hence, an appropriate local distance
checking approach is needed in the first place for designing
one-pass trajectory simplification algorithms.
...
Consider an error bound ζ and a sub-trajectory Ts [Ps ,
. . . , Ps+k ]. To achieve the local distance checking, OPERB
first dynamically maintains a directed line segment Li (i ∈
[1, k]), whose start point is fixed with Ps and its end point
is identified (may not in {Ps , . . . , Ps+i }) to fit all the previously processed points {Ps , . . . , Ps+i }. The directed line
segment Li is built by a function named fitting function F,
such that when a new point Ps+i+1 is considered, only its
distance to the directed line segment Li is checked, instead
of checking the distances of all or a subset of data points of
#
»
{Ps , . . . , Ps+i } to Ri+1 = Ps Ps+i+1 as the global distance
checking does. In this way, a data point is checked only once
during the entire process of trajectory simplification.
We next present the details of our fitting function F that
is designed for local distance checking.



ζ

Li = Li−1

when (|Ri | − |Li−1 |) ≤
(1)


4





|Li | = j ∗ ζ/2

ζ


when |Ri | > and |Li−1 | = 0
(2)
Li .θ = Ri .θ
4




 |Li | = j ∗ ζ/2







d(Ps+i , Li−1 )

 else (3)


 Li .θ = Li−1 .θ + f (Ri , Li−1 ) ∗ arcsin(
)/j
j ∗ ζ/2

#
»
where (a) 1 ≤ i ≤ k+1; (b) Ri−1 = Ps Ps+i−1 , is the directed
...
line segment whose end point Ps+i−1 is in Ts [Ps , . . . , Ps+k ];
(c) Li is the directed line segment built by fitting function
...
F to fit sub-trajectory Ts [Ps , . . . , Ps+i ] and L0 = R0 ; (d)
j = d(|Ri | ∗ 2/ζ − 0.5)e; (e) f () is a sign function such
that f (Ri , Li−1 ) = 1 if the included angle ∠(Ri−1 , Ri ) =
(Ri .θ − Li−1 .θ) falls in the range of (−2π, − 3π
], [−π, − π2 ],
2
π
3π
[0, 2 ] and [π, 2 ), and f (Ri , Li−1 ) = −1, otherwise; (f) ζ/2
is a step length to control the increment of |L|.
...
Given any sub-trajectory Ts [Ps , . . ., Ps+k ] and any error bound ζ, the expression j = d(|Ri | ∗ 2/ζ − 0.5)e in
the fitting function F essentially partitions the space into
zones around the center point Ps such that for each j ≥ 0,
# »
zone Zj = {Pj | j ∗ ζ/2 − ζ/4 < |Ps Pj | ≤ j ∗ ζ/2 + ζ/4},
i.e., the radii of Z0 , Z1 , Z2 and Z3 to Ps are in the ranges
of (− 14 ζ, 14 ζ], ( 14 ζ, 34 ζ], ( 34 ζ, 54 ζ] and ( 54 ζ, 47 ζ], respectively,
and all ranges have a fixed size ζ/2 as shown in Figure 5.
Moreover, the angle of the directed line segment Li is adjusted from Li−1 to make it closer to Ps+i than Li−1 , i.e.,
d(Ps+i , Li ) ≤ d(Ps+i , Li−1 ) for any i ∈ (s, s + k], and the
angle from L1 to Lk is bounded by a constant (Lemma 3).
The fitting
sub... function F also creates a virtual stepwise
#
»
trajectory Tv [Vs , . . ., Vs+l ] such that Vs = Ps , |Vs Vs+j | =
ζ/2 ∗ j (j ∈ [0, l], 0 < l ≤ k). For each point Ps+i in the sub
...
trajectory, it is mapped to a virtual point Vs+j in Tv locating
in zone Zj . Observe that (a) it is possible that (|Ri | −
|Li−1 |) ≤ 0, (b) the fitting function F forms a directed line
segment Li , which is closer to Ri...than Li−1 , and partitions
the points in the sub-trajectory T into two classes:

(1) Active points. Points Ps and Ps+i such that |Ri | − |Li−1 |
> ζ/4 are referred to as active points. An active point Ps+i
is mapped to the virtual point in zone Zj with j = d(|Ri | ∗
2/ζ − 0.5)e, and each zone has at most one active point.
(2) Inactive points. Points Ps+i such that |Ri |−|Li−1 | ≤ ζ/4
are referred to as inactivated points. For an inactive point
Ps+i , it is mapped to zone Zj with j = |Li−1 | ∗ 2/ζ. There
may exist none or multiple inactive points in a zone.
We next explain the fitting function F with an example.
Example 4: Consider the sub-trajectory [P0 , . . . , P7 ] in
Figure 5 whose eight points fall in zones Z0 , Z1 , Z2 , Z3 .
(1) Point P0 is the start point and the first active point, and
# »
L0 = R0 = P0 P0 .

# »
(2) Point P1 is inactive in zone Z0 , as |R1 | = |P0 P1 | < ζ4
and (|R1 | − |L0 |) ≤ ζ4 . Hence, L1 = L0 (case (1)).
(3) Point P2 is active in Z1 , as |R2 | > ζ4 and |L1 | = 0 .
Hence, |L2 | = ζ2 and L2 .θ = R2 .θ (case 2).
(4) Point P3 is inactive in Z1 , as (|R3 | − |L2 |) ≤ ζ4 . Hence,
L3 = L2 (case 1).
(5) Point P4 is active in Z2 , as |R4 |−|L3 |) > ζ4 and |L3 | 6= 0.
Hence, |L4 | = 2∗ ζ2 = ζ and the angle of L4 is also calculated
accordingly (case 3).
(6) Similarly, point P5 is active in Z3 (case 3), and points
P6 and P7 are inactive (case 1). Here P6 is mapped to Z3
as |L5 | = 32 ζ though it is physically located in zone Z2 . 2

4.2

Analyses of the Fitting Function

We next give an analysis of the fitting function F. First,
by the definition of F, it is easy to have the following.
...
Proposition 1: Given any sub-trajectory Ts [Ps , . . . , Ps+k ]
and error bound ζ, the directed line segment Li (i ∈ [1, k])
can be computed by the fitting function F in O(1) time. 2
The fitting function F also enables a local distance checking method, as shown below.
...
Theorem 2: Given any sub-trajectory Ts [Ps , . . . , Ps+k ] with
#
»
k ≤ 4 × 105 and error bound ζ, then d(Ps+i , Ps Ps+k ) ≤ ζ for
each i ∈ [0, k] if Ps+k is an active point and d(Ps+i , Li−1 ) ≤
ζ/2 for each i ∈ [1, k].
2
To prove Theorem 2, we first introduce a special class of
trajectories, based on which we show that Theorem 2 holds.
...
Stepwise trajectories. We say that a trajectory T [Ps , . . .,
Ps+k ] is stepwise w.r.t. ζ/2 if and only if |Ri | = i ∗ ζ/2 for
#
»
each directed line segment Ri = Ps Ps+i (i ∈ [0, k]).
Observe that |Ri | − |Ri−1 | = ζ/2 and d|Ri |∗2/ζ −0.5e
=i
...
(i ∈ [1, k]). Hence, for stepwise sub-trajectories T [Ps , . . .,
Ps+k ], the fitting function can be simplified as F0 below.


L1 = ζ/2



i = 1 (1)



L1 .θ = R1 .θ

|Li | = i ∗ ζ/2





d(Ps+i , Li−1 )  i ≥ 2 (2)



)/i
 Li .θ = Li−1 .θ + f (Ri , Li−1 ) ∗ arcsin(
i ∗ ζ/2

Stepwise trajectories have the following properties.
...
Lemma 3: Given any sub-trajectory Ts [Ps , . . . , Ps+k ] and
error bound ζ, if d(Ps+i , Li−1 ) ≤ ζ2 for each i ∈ [2, k], then
the angle
between L1 and Lk is bounded by ∆θ =
Pk change
o
1
1
lim
2
i=2 i ∗ arcsin( i ) < 0.8123 (or 46.54 ).
k→∞

Proof: By the revised fitting function F0 for a stepwise subtrajectory and d(Ps+i , Li−1 ) ≤ ζ2 for all i ∈ [2, k], we have
P
∆θ ≤ ki=2 1i ∗ arcsin( 1i ), which is monotonically increasing
√
2
with the increment of k. As x ≤ arcsin(x)
√ ≤ x/ 1 − x
1
1
(0 ≤ x < 1), we also have i ≤ arcsin i ≤ 1/ i2 − 1 (i ≥ 2).
Pk 1
√1 ) <
Hence, we have ∆θ ≤
lim
i=2 ( i ∗
i2 −1
k→∞
R∞ 1
1
1
1
π
1
√
√
√
(
∗
)dx
+
∗
=
+
≈
0.8123.
2
x
2
6
2
2 3
2
2
x −1

2 −1

...
Lemma 4: Given any sub-trajectory Ts [Ps , . . . , Ps+k ] with
#
»
k ≤ 4 × 105 and error bound ζ, then d(Ps+i , Ps Ps+k ) ≤ ζ for
ζ
each i ∈ [0, k] if d(Ps+i , Li−1 ) ≤ 2 for each i ∈ [1, k].
2

Figure 6: Example for the proof of Lemma 4
Proof: Consider the four directed line segments Ri =
#
»
#
»
Ps Ps+i , Rk = Ps Ps+k , Li−1 and Lk−1 shown in Figure 6.
Further, let β1 = Ri .θ − Li−1 .θ, β2 = Lk−1 .θ − Li .θ, β3 =
Rk .θ −Lk−1 .θ. We then adjust the included angles β1 as follows: (a) if π2 < |β1 | ≤ π, β1 = π - β1 , (b) if π < |β1 | ≤ 32 π,
β1 = β1 - π, (c) if 32 π < |β1 | ≤ 2π, β1 = 2π - β1 , and (d) β1
= |β1 |, otherwise. The included angle β3 is adjusted along
the same line as β1 , and β2 is bounded by Lemma 3.
Observe that d(Ps+i , Rk ) ≤ i ∗ ζ2 ∗ sin(|β1 | + |β2 | + |β3 |) ≤
P
1
1
1
i ∗ ζ2 ∗ sin(arcsin 1i + k−1
j=i+1 ( j ∗ arcsin j ) + arcsin k ). For
any k ≤ 4 × 105 , i ∗ sin(|β1 | + |β2 | + |β3 |) < 2, and, hence,
2
we have d(Ps+i , Rk ) < ζ2 ∗ 2 = ζ.
By mapping inactive and active points of a trajectory to
virtual points of a trajectory stepwise w.r.t. ζ/2, one can
readily prove Theorem 2 along the lines as Lemma 4.
Remarks. (1) Our fitting function achieves local distance
checking, as indicated by Proposition 1 and Theorem 2; (2)
...
For a sub-trajectory Ts [Ps , . . . , Ps+k−1 ] represented by a single directed line segment, we restrict k ≤ 4 ∗ 105 , which
suffices for the need of trajectory simplification in practice.

4.3

Algorithm OPERB

We are now ready to present our one-pass error bounded
algorithm, which makes use of the local distance checking
method based on the fitting function F.
The main result of this section is as follows.
...
Theorem 5: Given any trajectory T [P0 , . . . , Pn ] and error bound ζ, there exists a one-pass trajectory simplification
algorithm that is error bounded by ζ.
2
We prove Theorem 5 by providing such an algorithm for
trajectory simplification, referred
... to as OPERB shown in
Figure 7. Given a trajectory T [P0 , . . . , Pn ] and an error
bound ζ as input, algorithm OPERB outputs a compression
...
trajectory, i.e., a piecewise line representation T of T .
We first describe its procedure, and then present OPERB.
Procedure
getActivePoint. It takes as input a trajectory
...
T , a start point Ps , the current active point Pa , the current
directed line segment La and the error bound ζ, and finds
the next active point Pi . (1) When Pi = nil, it means that
no more active
... points could be found in the remaining subtrajectory T [Ps , . . . , Pn ]; (2) When f lag = true, it means
that the next active point Pi can be combined with the
current directed line segment La to form a new directed
line segment; Otherwise, (3) a new line segment should be
generated, and a new start point is considered.
It first increases a by 1 as it considers the data points
after Pa , and sets f lag to true (line 1). Secondly, by the
definition of the fitting function F, it finds the next active
point Pi (lines
2–6). Thirdly, if i = n + 1, then all data
...
points in T have been considered, hence, Pi is set to nil (line
7). Finally, (Pi , f lag) is returned (line 8).
...
Algorithm OPERB. It takes as input a trajectory T and
an error bound ζ, and returns the simplified trajectory T .

...
Algorithm OPERB(T [P0 , . . . , Pn ], ζ)

...
1. T := ∅; Pe := P0 ; (Pa , f lag) := getActivePoint(T , P0 , P0 , L0 , ζ);
2. while Pa 6= nil do {
# »
3.
Ps := Pe ; La = F(Pa , Ps Ps );
...
4.
(Pa , f lag) := getActivePoint(T , Ps , Pa , La , ζ);
5.
while Pa 6= nil & f lag = true do {
6.
La := F(Pa , La ); Pe := Pa ; ...
7.
(Pa , f lag) := getActivePoint(T , Ps , Pa , La , ζ); }
# »
8.
T := T ∪ {Ps Pe }; }
9. return T .
...
Procedure getActivePoint(T , Ps , Pa , La , ζ)
1. i := a + 1; f lag := true;
2. while ((|Ri | − |La |) ≤ ζ/4 & i ≤ n & (i − s) ≤ 4 × 105 do {
3.
if d(Pi , La ) > ζ/2 or d(Pi , Ra ) > ζ then
4.
f lag := false; break ;
5.
i := i + 1; }
6. if d(Pi , La ) > ζ/2 & |La | > 0 then f lag := false;
7. if i = n + 1 then Pi :=nil;
8. return (Pi , f lag).

Figure 8: A running example of algorithm OPERB.

4.4

Optimization Techniques

Figure 7: Algorithm OPERB

We further propose five optimization techniques for
OPERB to achieve a better compression ratio. The key idea
behind this is to (1) compress as many points as possible
with a directed line segment, or (2) to let the directed line
segment Li as close as possible to the current active point Pi
so that it has a higher possibility to represent Pi+1 . These
optimization techniques are organized by the processing order from the start to the end points of directed line segments.

After initializing
... (line 1), it then repeatedly processes the
data points in T one by one until all data points have been
considered, i.e., Pa = nil (lines 2–8). If Pa is not nil and
f lag is true, it means that Pa can be combined with the
current directed line segment La (lines 5–7). If f lag is false,
# »
then a directed line segment Ps Pe is generated and added
to T (line 8). Finally, the set T of directed
line segments,
...
i.e., a piecewise line segmentation of T , is returned (line 9).
We next explain algorithm OPERB with an example.

(1) Choosing the first active point after Ps . Algorithm OPERB calls procedure getActivePoint
to get the first
...
active point Pa in a sub-trajectory T [Ps+1 , . . . , Ps+k ] such
# »
that |Ps Pa | > ζ/4 (line 4 in Figure 7). However, as indicated by the fitting function F, we can replace Pa with
# »
the first point Pb such that |Ps Pb | > ζ, without affecting
the boundness of algorithm OPERB. This method potentially improves the compression ratio because more points
# »
# »
are covered by the directed line segment Ps Pb than Ps Pa ,
# »
# »
and Ps Pb is also closer to Pb than Ps Pa .

Example 5: Algorithm OPERB takes as input the trajectory and ζ shown in Figure 1, and its output is illustrated
in Figure 8. The process of algorithm OPERB is as follows.
(1) It initializes T with ∅, the last active point Pe with P0
and the current active point Pa with P1 (line 1).
(2) As Pa 6= nil (line 2), it then sets Ps = Pe = P0 and
# »
# »
La = F(Pa , Ps Ps ) = F(P1 , P0 P0 ) = L1 (line 3).
(3) It then calls getActivePoint() to get the next active point
Pa = P3 and f lag = true (line 4). As f lag = true means
that P3 can be combined with the current line segment La
= L1 , so it updates La to L3 , and Pe to P3 (line 6).
(4) Then it continues reading the next active point Pa =
P5 with f lag = true (line 7), and updates the current line
segment La to L5 , and Pe to P5 (lines 5, 6).
(5) It gets the next active Pa = P6 and f lag = false, as
d(P6 , L5 ) > ζ2 , meaning that P6 should not be compressed
to the current directed line segment (line 5). Hence, it adds
# » # »
Ps Pe = P0 P5 to T (line 8), sets Ps = Pe = P5 , and updates
# »
# »
La to F(Pa , Ps Ps ) = F(P6 , P5 P5 ) = L6 (line 3).
(6) The process continues until all points have been processed. At last, the algorithm outputs five continuous line
# » # » # » #
» #
»
segments {P0 P5 , P5 P6 , P6 P8 , P8 P10 , P10 P14 }.
2
Correctness & complexity analysis. The correctness of
algorithm OPERB follows from
... Theorem 2 immediately. Observe that for a trajectory T with n data points, the fitting
function F is called at most n times, and each data point is
considered once and only once. By Proposition 1, algorithm
OPERB runs in O(n) time. It is also easy to verify that algorithm OPERB takes O(1) space, as the directed line segment
in T can be output immediately once it is generated.
Note that this also completes the proof of Theorem 5.

(2) Adjusting
the distance condition. Given any sub
...
trajectory T [Ps , . . . , Ps+k ] and error bound ζ, let d+
max =
max{d(Ps+i , Li−1 ) | f (Ri , Li−1 ) = 1 and i ∈ [1, k]} and
d−
max = max{d(Ps+i , Li−1 ) | f (Ri , Li−1 ) = −1 and i ∈
[s + 1, s + k]}. Then the condition d(Ps+i , Li−1 ) ≤ ζ/2 in
+
Theorem 2 can be replaced with d−
max + dmax ≤ ζ, and
algorithm OPERB remains error bounded by ζ. Say, if
−
d+
max = 0.3ζ and dmax = 0.6ζ, then d(Ps+i , Lk ) for each
i ∈ [s, s + k] is still less than 0.3ζ + 0.6ζ = 0.9ζ < ζ.
Note that d(Ps+i , Li−1 ) ≤ ζ/2 implies d+
max ≤ ζ/2 and
−
+
d−
max ≤ ζ/2, and, hence, dmax + dmax ≤ ζ. Therefore,
+
d(Ps+i , Li−1 ) ≤ ζ/2 is a special case of d−
max + dmax ≤ ζ.
(3) Making L more close to the active points. When
OPERB calculates the angle Li .θ of an active point Pi , the
factor d(Pi , Li−1 ) in the fitting function F can be replaced
by a bigger number dx such that 0 ≤ dx ≤ d−
max when
f (Ri , Li−1 ) = −1 or 0 ≤ dx ≤ d+
max when f (Ri , Li−1 ) = 1,
to let Li be more close to Pi , under the restriction that
d(Pi ,Li−1 )
dx
)/j) is not larger than arcsin( j∗ζ/2
).
(arcsin( j∗ζ/2
(4) Incorporating
missing active points. For a sub...
trajectory T [Ps , . . . , Pa , . . . , Pa+i , . . . , Ps+k ], whereas Pa
and Pa+i are two consecutive active points. Let ja = d(|Ra |∗
2/ζ −0.5)e, ja+1 = d(|Ra+i |∗2/ζ −0.5)e and ∆j = ja+1 −ja .
If ∆j > 1, then there are no active points between zones Zja
and Zja+1 . In this case, we replace La+i .θ with La+i−1 .θ +
d(P

,L

)

∆j
a+i−1
f (Ra+i , La+i−1 ) ∗ arcsin( a+i
) ∗ ja+1
for the fitja+1 ∗ζ/2
ting function F, instead of La+i−1 .θ + f (Ra+i , La+i−1 ) ∗
d(P
,La+i−1 )
1
arcsin( a+i
) ∗ ja+1
to compensate the side effects
ja+1 ∗ζ/2
of missing active points to make the line La+i more closer
to Pa+i . Note that La+i−1 = La and ∆j > 0. Moreover,
d(Pa+i , La+i−1 ) could also be replaced by dx as above.

Figure 10: Practical restrictions on patch points.

Figure 9: Example anomalous line segments: the compression results of algorithms DP and OPERB on a subtrajectory with eleven points collected from a moving
vehicle running on an urban road network.
(5) Absorbing data points after Ps+k . Given any sub...
trajectory Ts [Ps , . . . , Ps+k , . . . , Ps+t ] and error bound ζ, if
#
»
[Ps , . . . , Ps+k ] is compressed to a line segment Ps Ps+k , then
#
»
any point Ps+t (t > k) can also be compressed to Ps Ps+k as
#
»
long as d(Ps+t , Ps Ps+k ) ≤ ζ such that OPERB can compress
more points into the directed line segment.
Remark. These optimization techniques are seamlessly integrated into OPERB, and Theorem 5 remains intact.

5.

AN AGGRESSIVE APPROACH

In this section, we introduce an aggressive one-pass trajectory simplification algorithm, referred to as OPERB-A,
which extends algorithm OPERB by further allowing trajectory interpolation under certain conditions, and even
achieves a better compression ratio than algorithm DP, the
existing LS algorithm with the best compression ratio.

5.1

Trajectory Interpolation

Existing line simplification algorithms, even the global
distance checking algorithm DP and our algorithm OPERB,
may generate a set of anomalous line segments.
...
Anomalous line segments. Consider a trajectory T [P0 ,
. . . , Pn ] and its piece-wise line representation T [R0 , . . . , Rm ]
(0 < m ≤ n) generated by an LS algorithm. A line segment
Ri (i ∈ [0,
...m]) is anomalous if it only represents two data
points in T , i.e., its own start and end points.
Anomalous line segments impair the effectiveness of trajectory simplification. We illustrate this with an example.
Example 6: Let us consider the compressing results of algorithms DP and OPERB on a sub-trajectory, shown in Figure 9, which has one crossroad between data points P3 and
P4 , and another crossroad between data points P7 and P8 .
Given the sub-trajectory and the error bound as shown in
Figure 9, algorithm DP returns four directed line segments
# » # » # » #
»
{P0 P3 , P3 P4 , P4 P7 , P7 P10 }, and algorithm OPERB out# » # » # » # »
puts five directed line segments {P0 P3 , P3 P4 , P4 P7 , P7 P8 ,
#
»
P8 P10 }, respectively. Observe that the directed line seg# »
# »
ments P3 P4 and P7 P8 are anomalous.
2
In this work, we propose the use of interpolating new data
points, referred to as patch points, into a trajectory under
certain conditions to reduce the number of anomalous line
segments to a large extent. The rational behind this is that
moving objects have sudden track changes while certain important data points may not be sampled due to various rea-

sons, especially on urban road networks. Note that slightly
changing the lines has proven useful in other disciplines [17].
Patch points. Let Ri−1 , Ri and Ri+1 be three continuous
directed line segments, where Ri is anomalous, i.e., Ri represents only two points. The patch point G w.r.t. Ri is the
intersection point between line segments Ri−1 and Ri+1 .
We next illustrate the use of patch points for reducing
anomalous line segments with an example.
Example 7: Consider Figure 9(2), where G1 , G2 are the
patch points w.r.t. R4 and R8 , respectively. After G1 and
G2 are interpolated, both algorithms DP and OPERB return
# » #
» #
»
three directed line segments {P0 G1 , G1 G2 , G2 P10 }, instead
of four and five, respectively, as shown in Example 6.
2
Patching method. Consider any three continuous directed
#
»
#
»
line segments, Ri−1 = Ps Ps+i−1 , Ri = Ps+i−1 Ps+i and
#
»
Ri+1 = Ps+i Pt such that Ri is anomalous and point Pt is
an active point and t > s + i. With the practical restrictions
and one-pass requirement, the patch point G w.r.t. Ri needs
to satisfy the conditions below, as illustrated by Figure 10.
#
»
# »
(1) Lying on the lines of Ps Ps+i−1 (i.e., Ps G.θ =
#
»
#
»
#
»
#
»
Ps Ps+i−1 .θ) and Ps+i Pt (i.e., GPs+i .θ = Ps+i Pt .θ),
# »
#
»
(2) |Ps G| ≥ (|Ps Ps+i−1 | − ζ/2), and
(3) the included angle from Ri−1 to Ri+1 falls in (−2π, −π−
γm ], [γm − π, π − γm ] and [π + γm , 2π), where γm ∈ [0, π] is
a parameter with γm = π3 by default.
Intuitively, these conditions are to incorporate the sudden
changes of moving directions implied in a trajectory. Note
that the restriction of the included angles may reduce the
chance of eliminating anomalous line segments. However, it
helps to produce more rational results.

5.2

Algorithm OPERB–A

We now present our algorithm OPERB-A that extends algorithm OPERB by introducing patch points. Recall that
algorithm OPERB starts a new directed line segment when
the distance of a point, say Pi , to the line segment Li−1 is
larger than ζ/2, marks the last active point Pa as Ps+i−1 ,
#
»
outputs the directed line segment Ri−1 = Ps Ps+i−1 , and
marks Ps+i−1 ...
as the new start point Ps of the remaining subjectify Ts [Ps+i−1 , . . . , Pn ]. However, for OPERB-A,
the line segment Ri−1 cannot be outputted until the patch
#
»
point G is determined when Ri = Ps+i−1 Ps+i is an AL,
and patch point G cannot be determined unless the angle of
#
»
Ri+1 = Ps+i Pt has been determined. Hence, different from
OPERB, OPERB-A uses a lazy output policy.
The lazy output policy. OPERB-A temporarily saves a
line segment in memory before outputting it, as follows:
(1) For simplicity, suppose that the line segment Ri−1 is not
anomalous and cannot be compressed with any more points.
OPERB-A saves it in memory first.
(2) It then compresses the subsequent points as OPERB to
the next line segment Ri until a broken condition is trig-

Data
Sets
Taxi
Truck
SerCar
GeoLife

Number of
Trajectories
12,727
10,368
11,000
182

Sampling
Rates(s)
60
1-60
3-5
1-5

PointsPer
Trajectory(K)
∼ 39.1
∼ 71.9
∼ 119.1
∼ 132.8

Total
points
498M
746M
1.31G
24.2M

Figure 11: A running example of OPERB-A.

Table 1: Real-life trajectory datasets

gered. If Ri is not anomalous, then it outputs Ri−1 and
saves Ri in memory. Otherwise, it marks Ri anomalous,
saves it, and moves to the next line segment Ri+1 .
(3) If Ri+1 is determined and Ri is anomalous, OPERB-A
checks the possibility of patching a point G w.r.t. Ri . If so,
# »
# »
it outputs Ps G, and GPt is temporarily saved; Otherwise, it
outputs Ri−1 and Ri , and Ri+1 is temporarily saved.
(4) The process repeats until all points have been processed.

sets of experiments to evaluate: (1) the execution time of
our approaches compared with algorithms DP and FBQS,
and the impacts of optimizations, (2) the compression ratios of our approaches compared with DP and FBQS, and
the impacts of optimizations, (3) the average errors of our
approaches compared with algorithms DP and FBQS, and
(4) the effectiveness of trajectory interpolation.

Remarks. All the optimization techniques in Section 4.4
remain intact, and are seamlessly integrated into OPERB-A.
We next explain algorithm OPERB-A with an example.
Example 8: Algorithm OPERB-A takes as input the trajectory and ζ shown in Figure 1, and its output is illustrated
in Figure 11. The process of OPERB-A is as follows.
# »
(1) It first creates L0 = R0 = P0 P0 , compresses P1 , . . . , P5
in turn, and generates L5 , along the same lines as OPERB.
(2) It then finds that d(P6 , L5 ) > ζ/2, which means that P6
# »
cannot be compressed into R5 = P0 P5 . R5 is temporally
saved. And the next line segment starts from P5 .
# »
(3) It then finds that d(P7 , L6 ) > ζ/2 and R6 = P5 P6 is an
AL. Hence, R6 is also temporally saved, and the next line
segment starts from P6 .
(4) It continues to compress points P7 and P8 in turn, and
generates L8 along the same lines as OPERB.
(5) It then finds that d(P9 , L8 )) > ζ/2, which means that
# »
R8 = P6 P8 is determined. Now OPERB-A tries to expand
the lines of R5 and R8 to get the intersection point G of
them, and uses it as the final start point of R8 . At last, R5
# »
is extended to P0 G and output as a directed line segment
# »
in the result, GP8 is temporarily saved and P8 becomes the
start point of the next line segment.
(6) The above process repeats until all points have been
processed. Finally, OPERB-A outputs four line segments
# » # » #
» #
»
{P0 G, GP8 , P8 P10 , P10 P14 }.
As shown in Figure 11, algorithm OPERB-A further elim# »
inates the directed line segment P5 P6 , compared with the
result of OPERB shown in Figure 8.
2
Correctness & complexity analysis. Observe that algorithm OPERB-A does not change the angle of any directed
line segment compared with OPERB, and hence it remains
error bounded. Moreover, each data point in a trajectory is
read once and only once in OPERB-A. Therefore, algorithm
OPERB-A is one-pass and error bounded. It is also easy to
verify that algorithm OPERB-A takes O(1) space, the same
as OPERB, as the directed line segment in T can be outputted immediately once it is generated. That is, the nice
properties of OPERB remain intact in OPERB-A.

6.

EXPERIMENTAL STUDY

In this section, we present an extensive experimental
study of our one-pass error bounded algorithms OPERB and
OPERB-A. Using four real-life datasets, we conducted four

6.1

Experimental Setting

Real-life Trajectory Datasets. We use four real-life
datasets shown in Table 1 to test our solutions.
(1) Taxi trajectory data, referred to as Taxi, is the GPS
trajectories collected by 12, 727 taxies equipped with GPS
sensors in Beijing during a period from Nov. 1, 2010 to Nov.
30, 2010. The sampling rate was one point per 60s, and Taxi
has 39, 100 data points on average per trajectory.
(2) Truck trajectory data, referred to as Truck, is the
GPS trajectories collected by 10,368 trucks equipped with
GPS sensors in China during a period from Mar. 2015 to
Oct. 2015. The sampling rate varied from 1s to 60s. Trajectories mostly have around 50 to 90 thousand data points.
(3) Service car trajectory data, referred to as SerCar,
is the GPS trajectories collected by a car rental company.
We chose 11, 000 cars from them, during Apr. 2015 to Nov.
2015. The sampling rate was one point per 3–5 seconds, and
each trajectory has around 119.1K data points.
(4) GeoLife trajectory data, refered to as GeoLife, is the
GPS trajectories collected in GeoLife project [25] by 182
users in a period from Apr. 2007 to Oct. 2011. These
trajectories have a variety of sampling rates, among which
91% are logged in each 1-5 seconds or each 5-10 meters per
point. The longest trajectory has 2,156,994 points.
Algorithms and implementation. We compared our
algorithms OPERB and OPERB-A with two existing LS
algorithms DP [6] and FBQS [12], and algorithms RawOPERB and Raw-OPERB-A, the counterparts of OPERB and
OPERB-A without optimizations, respectively.
(1) Algorithm DP is a classic batch LS algorithm with an
excellent compression ratio (shown in Figure 3).
(2) Algorithm FBQS is an online algorithm, and is the fastest
existing LS algorithm (recall Section 3.2).
(3) Algorithm OPERB combines the algorithm in Figure 7
and the optimization techniques in Section 4.4, while algorithm Raw-OPERB is the basic algorithm in Figure 7 only.
(4) Algorithms OPERB-A and Raw-OPERB-A are the aggressive solutions extending OPERB and Raw-OPERB with
trajectory interpolation, respectively.
All algorithms were implemented with Java. All tests were
run on an x64-based PC with 4 Intel(R) Core(TM) i5-4570
CPU @ 3.20GHz and 16GB of memory, and each test was
repeated over 3 times and the average is reported here.

6.2

Experimental Results

Figure 12: Efficiency evaluation: varying the size of trajectories.

Figure 13: Efficiency evaluation: varying the error bound ζ.

Figure 14: Efficiency evaluation: optimization techniques when varying the error bound ζ.

6.2.1

Evaluation of Compression Efficiency

In the first set of tests, we compare the efficiency (execution time) of our approaches OPERB and OPERB-A with
algorithms DP and FBQS and with algorithms Raw-OPERB
and Raw-OPERB-A. For fairness, we load and compress trajectories one by one, and only count the running time of the
compressing process.
Exp-1.1: Impacts of the sizes of trajectories. To evaluate the impacts of the number of data points in a trajectory
(i.e., the size of a trajectory), we chose 100 trajectories from
Taxi, ...
Truck, SerCar and GeoLife, respectively, and varied the
size |T | of trajectories from 2, 000 to 10, 000, while fixed
ζ = 40 meters (m). The results are reported in Figure 12.
(1) Algorithms OPERB, OPERB-A and FBQS scale well with
the increase of the size of trajectories on all datasets, and
show a linear running time, while algorithm DP does not.
This is consistent with their time complexity analyses.
(2) Algorithms OPERB and OPERB-A are the fastest LS
algorithms, and are (3.8–5.3, 3.5–4.8, 4.6–7.2, 6.2–8.4) times
faster than FBQS, and (9.6–17.6, 8.8–15.4, 8.4–16.3, 9.0–
14.4) times faster than DP on (Taxi, Truck, SerCar, GeoLife),
respectively. The running time of OPERB and OPERB-A is
similar, and the difference is below 10%.
Exp-1.2: Impacts of the error bound ζ. To evaluate
the impacts of ζ, we varied ζ from 10m to 100m on the entire

Taxi, Truck, SerCar and GeoLife, respectively. The results are
reported in Figure 13.
(1) All algorithms are not very sensitive to ζ, but their running time all decreases a little bit with the increase of ζ,
as the increment of ζ decreases the number of directed line
segments in the output. Further, algorithm DP is more sensitive to ζ than the other three algorithms.
(2) Algorithms OPERB and OPERB-A are obviously faster
than DP and FBQS in all cases. OPERB is on average (13.9,
17.4, 14.7, 20.6) times faster than DP, and (4.1, 4.1, 5.4, 5.2)
times faster than FBQS on (Taxi, Truck, SerCar, GeoLife), respectively. Algorithm OPERB-A is as fast as OPERB because
trajectory interpolation is a light weight operation.
Exp-1.3: Impacts of optimization techniques. To
evaluate the impacts of our optimization techniques (see
Section 4.4), we compared algorithms OPERB and OPERBA with Raw-OPERB and Raw-OPERB-A, respectively. We
chose 500, 1000 and 500 trajectories from Taxi, Truck, SerCar
and GeoLife, respectively, and varied ζ from 10m to 100m.
The results are reported in Figure 14.
(1) The running time of all algorithms slightly decreases
with the increase of ζ, consistent with Exp-1.2.
(2) The running time of Raw-OPERB is (85.0%, 79.6%,
90.4%, 100.4%) of OPERB on average on (Taxi, Truck,
SerCar, GeoLife), respectively, and the running time of RawOPERB-A is (91.3%, 90.1%, 91.6%, 101.5%) of OPERB-A on

Figure 15: Effectiveness evaluation: varying the error bound ζ.

Figure 16: Effectiveness evaluation: optimization techniques when varying the error bound ζ.
average on (Taxi, Truck, SerCar, GeoLife), respectively. This
shows that the optimization techniques have a limited impact on the efficiency of OPERB and OPERB-A. However,
as will be shown immediately, the benefits of compression
ratios are highly appreciated.

6.2.2

Evaluation of Compression Effectiveness

In the second set of tests, we compare the compression
ratios of our algorithms OPERB and OPERB-A with DP
and FBQS and with Raw-OPERB and...Raw-OPERB-A,
re...
spectively. Given a set of trajectories {T1 , . . . , TM } and their
piecewise line representations {T1 , . . . , TM }, the compression
P
PM ...
ratio is ( M
j=1 |T j |)/(
j=1 |T j |). Note that by the definition, algorithms with lower compression ratios are better.
Exp-2.1: Impacts of the error bound ζ. To evaluate
the impacts of ζ on compression ratios of these algorithms,
we varied ζ from 5m to 100m on the entire four datasets,
respectively. The results are reported in Figure 15.
(1) When increasing ζ, the compression ratios decrease. For
example, in SerCar, the compression ratios are greater than
28.7% when ζ = 5m, but are less than 6.6% when ζ = 100m.
(2) GeoLife has the lowest compression ratios, compared with
Taxi, Truck and SerCar, due to its highest sampling rate, Taxi
has the highest compression ratios due to its lowest sampling
rate, and Truck and SerCar have the compression ratios in
the middle accordingly.
(3) First, algorithm OPERB has comparable compression
ratios with FBQS and DP. For example, when ζ = 40m,
the compression ratios are (20.9%, 20.4%, 11.1%, 3.1%) of
FBQS, (20.7%, 18.7%, 8.9%, 2.6%) of DP and (22.3%, 20.3%,
10.0%, 2.6%) of OPERB on (Taxi, Truck, SerCar, GeoLife),
respectively. For all ζ, the compression ratios of OPERB
are on average (107.2%, 98.3%, 92.9%, 85.1%) of FBQS and
(107.7%, 106.6%, 113.5%, 99.6%) of DP on (Taxi, Truck,
SerCar, GeoLife), respectively. OPERB is better than FBQS
on Truck, SerCar and GeoLife, while a little worse on Taxi.
The results also show that OPERB has a better performance
than FBQS on datasets with high sampling rates.

Second, algorithm OPERB-A achieves the best compression
ratios on all datasets and nearly all ζ values. Its compression
ratios are on average (83.7%, 79.5%, 79.7%, 81.0%) of FBQS
and (84.2%, 86.4%, 97.1%, 94.7%) of DP on (Taxi, Truck,
SerCar, GeoLife), respectively. Similar to OPERB, OPERB-A
has advantages on datasets with high sampling rates.
Exp-2.2: Impacts of the optimization techniques.
We compared algorithms OPERB and OPERB-A with RawOPERB and Raw-OPERB-A, respectively. We varied ζ from
5m to 100m on the entire Taxi, Truck, SerCar and GeoLife,
respectively. The results are reported in Figure 16.
(1) The optimizations have great impacts on the compression ratios of OPERB and OPERB-A. Indeed, OPERB is
on average (87.9%, 71.8%, 61.8%, 58.0%) of Raw-OPERB,
and OPERB-A is on average (93.1%, 88.5%, 77.1%, 78.5%)
of Raw-OPERB-A on (Taxi, Truck, SerCar, GeoLife), respectively. Note that the optimization techniques have a better
impact on datasets with high sampling rates.
(2) The impacts of the optimization techniques increase with
the increase of ζ on Taxi and Truck. For example, OPERB is
(92.1%, 87.3%, 82.6%) of Raw-OPERB on Taxi, and (78.5%,
70.9%, 63.7%) of Raw-OPERB on Truck when ζ = (10, 40,
100), respectively. It is similar for algorithm OPERB-A.
Exp-2.3: Distribution of line segments. To further
evaluate the difference of the compression results of these
algorithms, we chose 100 trajectories from each of (Taxi,
Truck, SerCar, GeoLife), while fixed ζ = 40m. For a T =
(L1 , L2 , · · · , LM ) derived from trajectories by a compression
algorithm, we count the number of points, Ci , included in
each Li , then let Z(k) = |{Ci |Ci = k}|, i.e., Z(5) means
the number of all Li containing 5 data points. Note that
the start/end points are repeatedly counted for adjacent line
segments, and, hence, there may be some lines having only
one point. The results are reported in Figure 17.
(1) Algorithms OPERB-A and DP produce more line segments containing large number of points (heavy line segments) than FBQS and OPERB. Heavy line segments are
closely related to compression ratios, and help to decrease

Figure 17: Effectiveness evaluation: distribution of line segments. The horizontal coordinate is the number k of data
points, and the vertical coordinate is the number Z(k) of line segments containing k points.

Figure 18: Evaluation of average errors: varying the error bound ζ.
compression ratios. The distribution of line segments is consistent with the compression ratios shown above.
(2) Algorithm OPERB has the largest number of line segments containing only one point. However, they are reduced
by OPERB-A to a large extent.

6.2.3

Evaluation of Average Errors

In the third set of tests, we evaluate the average errors of
these algorithms. We varied ζ from 5m to 100m on the entire
Taxi, Truck, SerCar
and
...
... GeoLife, respectively. Given a set of
trajectories {T1 , . . . , TM } and their piecewise line representations {T
... 1 , . . . , TM }, and point Pj,i denoting a point in trajectory T j contained in a line segment Ll,i ∈ Tl (l ∈ [1, M ]),
P
PM
PM ...
then the average error is M
j=1
i=0 d(Pj,i , Ll,i )/
j=1 |T j |.
The results are reported in Figure 18.
(1) Average errors obviously increase with the increase of
ζ. Taxi also has the lowest average errors than Truck and
SerCar for all algorithms, as it has the highest compression
ratios, and SerCar has the highest average errors, as it has
the lowest compression ratios among the three datasets.
(2) Algorithm DP not only has better compression ratios,
but also has lower average errors than algorithm FBQS on
all datasets and most ζ values.
(3) Algorithms OPERB and OPERB-A have similar average
errors with each other. Meanwhile, OPERB-A does not introduce extra error. Compared with DP and FBQS, their errors
are a litter smaller on Taxi and a little larger on SerCar.

6.2.4

Evaluation of Trajectories Interpolation

In the last set of tests, we evaluate the lazy trajectory
interpolation policy of algorithm OPERB-A.
Exp-4.1: Patching ratios. To evaluate the patching ratios of OPERB-A and the impacts of ζ on patching ratios,
we varied ζ from 10m to 100m, while fixed γm = π/3, on
Taxi, Truck, SerCar and GeoLife, respectively. The patching
N
ratio is defined as Nap ∗ 100%, where Np is the number of
patching points successful added to the trajectories, and Na

Figure 19: Patching ratios of OPERB-A.
is the number of anonymous line segments before trajectory
interpolation. The results are reported in Figure 19–(1).
(1) The patching ratios are on average (50.5%, 60.3%,
63.2%, 51.5%) on (Taxi, Truck, SerCar, GeoLife), respectively.
That is, more than half of the anomalous line segments are
successfully eliminated by the lazy trajectory output policy.
(2) The patching ratios on Taxi, Truck, SerCar and GeoLife
decrease from ζ = 30m or ζ = 40m, respectively.
(3) Taxi has the lowest patching ratios due to its relatively
lower sampling rate. Moreover, the number of anomalous
line segments output by OPERB-A is significantly less than
the other algorithms. That is, even a patching ratio like
50.5% is enough to improve the compression ratio and to
make OPERB-A have the best compression ratio.
Exp-4.2: Impacts of γm for trajectory interpolation.
Our trajectory interpolation uses a parameter γm ∈ [0, π]
to restrict the included angle of two line segments. Note
that a smaller γm means that a larger direction change is
allowed in trajectory interpolation. To evaluate the impacts
of γm on patching ratios, we randomly chose 100 trajectories
from each of (Taxi, Truck, SerCar), and we varied γm from
0o to 180o (or 0 to π), while fixed ζ = 40m. The results are
reported Figure 19–(2).
(1) When varying γm , the patching ratio decreases with the
increase of γm . The patching ratio decreases (a) slowly when
γm ∈ [0, 75o ], (b) fast when γm ∈ (75o , 145o ), and (c) fastest

when γm ∈ (145o , 180o ]. The region [30o , 90o ] is the candidate region for γm with both high patching ratios and reasonable patch points, not too far away from the points Ps+k
and Ps+k+1 , between which the patch point is interpolated.
Hence, we set γm = π/3 by default.
(2) Parameter γm has different impacts on different data
sets. The patching ratio of Taxi decreases quickly when γm ∈
[80o , 120o ], it is the result of taxies running on urban road
networks, which have more crossroads. The patching ratio
of Truck decreases slowly in this region because many trucks
are running in suburban districts or between cities, in which
there are less crossroads.
Summary. From these tests we find the following.
(1) Efficiency. OPERB and OPERB-A are the fastest algorithms, which are on average (13.9, 17.4, 14.7, 20.6) times
faster than DP, and (4.1, 4.1, 5.4, 5.2) times faster than
FBQS on (Taxi, Truck, SerCar, GeoLife), respectively.
(2) Compression ratios. (a) OPERB is comparable with
FBQS and DP. Its compression ratios are on average
(107.2%, 98.3%, 92.9%, 85.1%) of FBQS and (107.7%,
106.6%, 113.5%, 99.6%) of DP on (Taxi, Truck, SerCar,
GeoLife), respectively, and OPERB has a better performance
on trajectories with higher sampling rates. (b) OPERB-A
has the best compression ratios on all datasets and nearly
all ζ values. Its compression ratios are on average (83.7%,
79.5%, 79.7%, 81.0%) of FBQS and (84.2%, 86.4%, 97.1%,
94.7%) of DP on (Taxi, Truck, SerCar, GeoLife), respectively.
It shows its advantage on trajectories with both high and
low sampling rates. (c) The optimization techniques are effective for algorithms OPERB and OPERB-A on all datasets.
(3) Average errors. Algorithm OPERB has similar average
errors with OPERB-A. They have lower average errors than
the other algorithms on Taxi while higher on SerCar.
(4) Patching ratios. OPERB-A successfully eliminates more
than a half of anomalous line segments by patching data
points, which improves the compression ratio, and indeed
makes it achieve the best compression ratio.

7.

CONCLUSIONS AND FUTURE WORK

We have proposed OPERB and OPERB-A, two one-pass
error bounded trajectory simplification algorithms. First,
we have developed a novel local distance checking approach,
based on which we then have designed OPERB, together
with optimization techniques for improving its compression
ratio. Second, by allowing interpolating new data points
into a trajectory under certain conditions, we have developed an aggressive one-pass error bounded trajectory simplification algorithm OPERB-A, which has significantly improved the compression ratio. Finally, we have experimentally verified that both OPERB and OPERB-A are much
faster than FBQS, the fastest existing LS algorithm, and in
terms of compression ratio, OPERB is comparable with DP,
and OPERB-A is better than DP on average, the existing LS
algorithm with the best compression ratio.
A couple of issues need further study. We are to incorporate semantic based methods and to study alternative forms
of fitting functions to further improve the effectiveness of
trajectory compression.
Acknowledgments.
This work is supported in part
by NSFC U1636210, 973 Program 2014CB340300 & NSFC
61421003. For any correspondence, please refer to Shuai Ma.

8.

REFERENCES

[1] Extended version and datasets.
http://mashuai.buaa.edu.cn/traj.html.
[2] H. Cao, O. Wolfson, and G. Trajcevski. Spatio-temporal
data reduction with deterministic error bounds. VLDB J.,
15(3):211–228, 2006.
[3] M. Chen, M. Xu, and P. Franti. A fast multiresolution
polygonal approximation algorithm for GPS trajectory
simplification. TIP, 21(5):2770–2785, 2012.
[4] Y. Chen, K. Jiang, Y. Zheng, C. Li, and N. Yu. Trajectory
simplification method for location-based social networking
services. In GIS-LBSN, 2009.
[5] A. Civilis, C. S. Jensen, and S. Pakalnis. Techniques for
efficient road-network-based tracking of moving objects.
TKDE, 17(5):698–712, 2005.
[6] D. H. Douglas and T. K. Peucker. Algorithms for the
reduction of the number of points required to represent a
digitized line or its caricature. The Canadian Cartographer,
10(2):112–122, 1973.
[7] R. Gotsman and Y. Kanza. A dilution-matching-encoding
compaction of trajectories over road networks. In
GeoInformatica, 2015.
[8] J. Hershberger and J. Snoeyink. Speeding up the
douglas-peucker line-simplification algorithm. Technical
Report, University of British Columbia, 1992.
[9] C. C. Hung, W. Peng, and W. Lee. Clustering and
aggregating clues of trajectories for mining trajectory
patterns and routes. VLDB J., 24(2):169–192, 2015.
[10] S. Kaul, M. Gruteser, V. Rai, and J. Kenney. On predicting
and compressing vehicular GPS traces. In Vehi-Mobi, 2010.
[11] E. J. Keogh, S. Chu, D. M. Hart, and M. J. Pazzani. An
online algorithm for segmenting time series. In ICDE, 2001.
[12] J. Liu, K. Zhao, P. Sommer, S. Shang, B. Kusy, and
R. Jurdak. Bounded quadrant system: Error-bounded
trajectory compression on the go. In ICDE, 2015.
[13] C. Long, R. C.-W. Wong, and H. Jagadish.
Direction-preserving trajectory simplification. PVLDB,
6(10):949–960, 2013.
[14] C. Long, R. C.-W. Wong, and H. Jagadish. Trajectory
simplification: on minimizing the direction-based error.
PVLDB, 8(1):49–60, 2014.
[15] N. Meratnia and R. A. de By. Spatiotemporal compression
techniques for moving point objects. In EDBT, 2004.
[16] R. Metha and V.K.Mehta. The Principles of Physics for
11. S Chand, 1999.
[17] J. S. B. Mitchell, V. Polishchuk, and M. Sysikaski.
Minimum-link paths revisited. Computational Geometry,
47(6):651–667, 2014.
[18] J. Muckell, P. W. Olsen, J.-H. Hwang, C. T. Lawson, and
S. S. Ravi. Compression of trajectory data: a
comprehensive evaluation and new approach.
GeoInformatica, 18(3):435–460, 2014.
[19] A. Nibali and Z. He. Trajic: An effective compression
system for trajectory data. TKDE, 27(11):3138–3151, 2015.
[20] I. S. Popa, K. Zeitouni, VincentOria, and A. Kharrat.
Spatio-temporal compression of trajectories in road
networks. GeoInformatica, 19(1):117–145, 2014.
[21] K.-F. Richter, F. Schmid, and P. Laube. Semantic
trajectory compression: Representing urban movement in a
nutshell. J. Spatial Information Science, 4(1):3–30, 2012.
[22] F. Schmid, K. Richter, and P. Laube. Semantic trajectory
compression. In SSTD, 2009.
[23] W. Shi and C. Cheung. Performance evaluation of line
simplification algorithms for vector generalization.
Cartographic Journal, 43(1):27–44, 2006.
[24] R. Song, W. Sun, B. Zheng, and Y. Zheng. PRESS: A novel
framework of trajectory compression in road networks.
PVLDB, 7(9):661–672, 2014.
[25] Y. Zheng, X. Xie, and W. Ma. GeoLife: A collaborative
social networking service among user, location and
trajectory. IEEE Data Eng. Bull., 33(2):32–39, 2010.

