DEIM Forum 2013 A5-3

Implementation and Experiments of Frequent GPS Trajectory Pattern
Mining Algorithms
Xiaoliang GENG† , Hiroki ARIMURA† , and Takeaki UNO††† Graduate School of Information Science and Technology, Hokkaido University
Kita 14, Nishi9, Kita–ku, Sapporo, Hokkaido, 060–0814 Japan†† National Institute of Informatics
2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
Abstract Trajectory data could be analyzed through the discovery of patterns. In this paper, we propose a novel
pattern named frequent envelope pattern (FEVP) of trajectory data. A frequent envelope pattern is a length-width-bounded area generated by a given trajectory data set of X. And this pattern includes all trajectory data
in X. We consider the problem of searching all frequent envelope patterns. We give mining an algorithm and show
the results.
Key words trajectory mining, spatio-temporal data, frequent data mining

1. Introduction

be a collection of m two-dimensional discrete trajectories,
called a trajectory database, whose trajectory is a sequence

Recent years, smart mobile devices for example smartof 2-dim points si = (pij )n
j=1 having the same length n.

phone with GPS sensors become more and more popular.

Then, an envelope pattern(EVP ) of width θ > 0 and lengthℓ >= 0 is a triple P (X) = (X, EX , st, ed) of a sequence

As a result, massive amount of spatio-temporal informationsuch as real GPS stream data has attracted many researchers
to extracting interesting information from it [1], [2].
In this paper, we address the problem of mining trajectory

EX = (M BR(X1 ), . . . , M BR(Xℓ )) of ℓ = ed − st + 1 rectangles, and time steps st <= ed. P says that there are some set
X of k moving objects that have locations close each otherpattern from trajectory database. For solving this problem,

contained in squares M BR(X1 ), . . . , M BR(Xℓ ) at consecu-

many researchers have proposed many algorithms [1], [4],tive ℓ time stamps. Fig. 1 shows an example of an envelope[5], [6]. These algorithms are based on flock pattern min-pattern.

ing [1], [4] and moving cluster [5], [6]. Some of their algo-

In the above definition of EVP , there can be potentiallyrithms are very eﬀective. Their experiments support that

infinitely many similar patterns for the continuous nature of

their algorithms take good performance.

space domain. To overcome this problem, we then introduce

However, searching interesting trajectory pattern could be

the class FEVP of frequent envelope patterns, and study aquite diﬃcult. First, trajectory data is 2 dimensional data

mining problem for constrained frequent envelope patterns.

with time stamps. Traditional method of data mining for

As a main result, we present an eﬃcient algorithm BEM

item set does not work. Second, trajectory data always in-that, given maximal width θ, minimal length ℓ, and minimal

cludes time stamp such as GPS trajectory data stream. It issize σ, finds all frequent envelope patterns in a trajectorya problem that how to use time stamps. What is more, GPSdatabase. The algorithm uses depth first search to enumer-

trajectory data stream could be dense or sparse. The prun-

ate all the subsets of database and check them whether could

ing strategy may not eﬃciently work, the algorithm may notform FEVPs. Finally, it finds out all the frequent envelope

judge the data correctly.

patterns.

Moreover, the algorithm of mining trajectory data has toIn summary, our algorithm has the following advantages.

store large amount of trajectory data to analyze. As a result,（ 1 ） Depth first recursive enumeration of frequent pat-this algorithm should save memory as much as possible. Tra-

terns,

jectory data is always on-line real data stream, the algorithm（ 2 ） No duplication of frequent trajectory patterns,

should be fast enough to deal with that.

（ 3 ） Generating any frequent pattern from database.

In our paper, we define the pattern as follows. Let m andn be any non-negative integers. Let S = { si | i = 1, . . . , m }To examine basic characteristics of our algorithm, we doexperiments and show them in Sec.4.

the sets of all x- and y-coordinates of the points in Sj . We
assume that S, m, and n are fixed, otherwise stated.
2. 2 Trajectory envelope patterns
For a rectangle R = [x0 , x1 ] × [y0 , y1 ] in R2 , the widthof R is given by width(R) = max{|x1 − x0 |, |y1 − y0 |}.
The minimum bounding rectangle (MBR) containing Sj isgiven by MBR(Sj ) = [x0 , x1 ]×[y0 , y1 ], where x0 = min Sjx ,x1 = max Sjx and y0 = min Sjy , y1 = max Sjy . If Sj = ∅,then MBR(Sj ) = ∅, too. We know that MBR(Sj ) gives theunique and minimal area within all axis-parallel rectangles
that contain Sj .
Let S = {S1 , . . . , Sm } be trajectory database and X ⊂=S
be a subset of S, a 2-dim trajectory envelope pattern (oran envelope pattern, EVP ) of length ℓ in S is a quadruple
図 1 A 2-dim envelope pattern P (X1 ) = (X1 , (M BR1 , M BR2 ,M BR3 ), 3, 5) in R2 containing three moving objects 2, 3, 4
at time stamps t3 , t4 , and t5 in a set of trajectories, where
M BR1 , M BR2 , and M BR3 are minimal bounding rectangles with width <= θ. X1 is the set of trajectory data ofmoving objects of 2, 3, 4.

This paper is organized as follows. Sec. 2. gives basic definitions, and Sec. 2. 4 studies frequent envelope patterns. Sec.
3. presents our algorithm and Sec. 4. shows experimental
results. Finally, Sec. 5. concludes.

P (X) = (X, EX , st, ed), where（ 1 ） Time stamps st and ed which 0 <= st <= ed <= n arecalled the start and end time such that ℓ = ed − st + 1.
（ 2 ） EX = Est,ed (X) = (M BR(Xst ), . . . , M BR(Xst+ℓ−1 ))is a ℓ-tuple of 2-dim rectangles.
The width of P (X) is w = maxst<
width(M BR(Xj )).
=j <=edWe denote by start(P (X)) = st, end(P (X)) = ed,len(P (X)) = ℓ, and width(P (X)) = w. If ℓ = 0, thenP∅ (X) = (X, ⟨⟩, st, st) is the empty pattern, and we definelen(P (X)) = 0 and width(P (X)) = 0.

2. Preliminaries
In this section, we give the basic definitions and concepts
on trajectory pattern mining.
2. 1 Two-dimensional discrete trajectory data
Let N = {0, 1, 2, . . .} and R denote the sets of all naturaland all real numbers, respectively. For any i, j ∈ N (i <= j)and any a, b ∈ R (a <= b), we define the intervals [i..j] =∗{i, . . . , j} and [a, b] = { x ∈ R | a <=x<= b }. For a set A, A
denotes the set of all possibly empty sequences over A. Fora sequence s = ⟨a1 , . . . , an ⟩ of n elements from A, we define|s| = n, s[i] = ai , and s[i..j] = ai ai+1 · · · aj . The empty
sequence is denoted by ⟨⟩.
A point in R2 is a pair p = (x, y) ∈ R2 . Let si (1 <=i<= m)be a sequence si = (pi1 , . . . , pin ) = (pij )n
j=1 of n points in 2dimensional space R2 with sampled at time-stamps, called adiscrete trajectory or trajectory, which n >= 0 denotes thelength of a trajectory.

S = {s1 , . . . , sm } is a trajectory

database whose elements (points) si [j] = pij = (xij , yji ) ∈ R2
stands for the location of object 1 <= m at time stamp=i<1<= n and |S| = m. We consider i as the id of one trajec=j<tory data. Note that all trajectories in S have exactly samelength n in our definition. For each time stamp 1 <= n,=j<
we define Sj = {(xij , yji ) | 1 <= m}. Sj is the set of all the=i<points in time stamp j belonging to all trajectory data in S.
Let Sjx = {xj | (xj , yj ) ∈ Sj } and Sjy = {yj | (xj , yj ) ∈ Sj } be［Example 1］ In Fig. 1, we show an example of an enve-

lope pattern P (X1 ) = (X1 , (M BR1 , M BR2 , M BR3 ), 3, 5) oflength 3, such that X1 is the set of trajectory data of moving
objects of 2, 3, and 4. We see that P (X1 ) contains trajectorydata of moving objects 2, 3, and 4 among trajectory data offive moving objects at time stamps t3 , t4 , and t5 .
2. 3 Frequent trajectory envelope pattern［Definition 1］ We call a trajectory envelope pattern

P (X) = (X, EX , st, ed) a candidate trajectory envelope pattern (CandEVP , for short) given by non-negative constraints
θ and ℓ, if P (X) satisfies the following conditions:（ 1 ） len(P (X)) >= ℓ,（ 2 ） width(P (X)) <= θ.

We call ℓ minimal length(min-length, for short) of CandEVP
and call θ maximal width(max-width, for short) of CandEVP.
［Definition 2］ We call a candidate trajectory envelope pat-tern P (X) = (X, EX , st, ed) with constraints θ and ℓ a frequent trajectory envelope pattern (FEVP , for short) given bya non-negative constraint σ, if P (X) satisfies | X |>= σ. We
call σ minimal size(min-size, for short) of CandEVP.
［Definition 3］ For any 1 <= ed, we denote by= st <F EVP(S, st, σ, θ, ℓ), the class of all frequent envelope patterns FEVP with starting position st, X ⊂=S, and nonnegative constraints σ, θ, and ℓ.

Algorithm 1 The main algorithm for finding all frequent

Algorithm 3 Check CandEVP algorithm

envelope patterns

1: procedure CheckCandEVP(X, start, S, Θ)

1: procedure main(S, θ, ℓ, σ)

2:Y ← X;

3:get σ from Θ4:

get ℓ from Θ5:

if len(Y ) < ℓ then2:Θ ← (θ, ℓ, σ);3:

for i ← 1, . . . , n − ℓ + 1 do

4:start ← i5:

for c ← 1, . . . , m do
BEM(c, ∅, start, S, Θ);6:

end for7:

6:

end if8:

for i ← Y [1, . . . , len(Y )] do

end for9:

9: end procedure

10:

8:

11:

Algorithm 2 Basic frequent envelope trajectory patterns
1: procedure BEM(c, X, start, S, Θ)2:

Y ← X;

3:for i ← S[sc , . . . , sm ] do∪
Y ← Y {i}4:if CheckCandEVP(Y, start, S, Θ) then5:get θ from Θ
if | Y |>= θ then

6:7:Output Y as FEVP;

8:

end if9:

BEM(i, Y, start, S, Θ)

10:

end if

11:
12:

end for

13: end procedure

return FALSE

7:

if width(MBR(Yi )) > σ thenreturn FALSE
end if

12:

end for13:

return TRUE

14: end procedureℓ > 0, and σ >= 1. Next it invokes the recursive sub-procedure
BEM in Alg.2 with each singleton trajectory data c andother arguments in line 6. BEM algorithm enumerates all
subsets of S and calls the algorithm CheckCandEVP tocheck whether these subsets could form CandEVPs.
3. 2 Basic envelope trajectory pattern miner algorithm BEM
3. 2. 1 Enumerate subsets of S
Algorithm BEM depth first enumerates subsets of S. For
every subset, this algorithm calls CheckCandEVP in line 5

2. 4 Frequent pattern mining problem

to check whether it could form a CandEVP. If this subset is

The number of all possible FEVPs in a given database S

a CandEVP, BEM checks the size of it. If the size is no lessmay be prohibitive. Thus, we incorporate a set of constraints

than θ, this subset is outputted as a FEVP; else, recursively

as well as closeness into our envelope pattern mining prob-

call BEM itself for further searching. If this subset is not alem. Now, we state our problem as follows.

CandEVP, this algorithm prunes this subset and requires a

Frequent Envelope Pattern Mining Problem:
Input: A collection S = {s1 , . . . , sm } of 2-dim trajectories
with real numbers of max-width θ > 0, min-length ℓ > 0,and min-size σ >= 1.
Output:Find all frequent envelope patterns P (X) in

FEVP(S, st, θ, ℓ, σ) (X ⊂=S) appearing in S such thatwidth(P (X)) <= θ, len(P (X)) >= ℓ, and | X |>= σ without
duplicates.

3. Proposed Algorithm
We present an algorithm BEM (Basic envelope pattern

new subset.
3. 2. 2 Call CheckCandEVPAlgorithm CheckCandEVP checks a subset X of trajectory data with the constrains of start, S, θ, ℓ. It computes
the MBR from start time stamp to the end of trajectorydata or the computation stops at the time stamp where thewidth(MBR) > θ. Next, this algorithm computes the length
by end − start + 1. If the length >= ℓ, it returns TRUE; else
it returns FALSE.
3. 3 Analysis
Combining the above arguments, we give the correctness
and the complexity of our main algorithm. Let m be theminer) for mining frequent envelope trajectory patterns un-

size of input database S and n be the length of trajectory

der given constraints from an input trajectory database.

data. The main algorithm search from start time stamp

3. 1 Outline of our algorithmof trajectory data to n − ℓ + 1. Therefore, the complexity

In Alg.1, Alg.2 and Alg.3, we present the main algorithmof main is O(n). The enumeration of subsets of trajectorymain, its recursive sub-procedure BEM and checking Can-data taken by BEM and main enumerates 2m subsets ofdEVP algorithm CheckCandEVP respectively.

S at most. For checking them one by one, the complexity

The main algorithm BEM in Alg.1 first receives an input trajectory database S and constraint parameters θ > 0,of CheckCandEVP is O(n log m). Clearly, the total complexity is O(m2m n log m).

60

6

900
700

40
30

6

20

6

10
0

6

800

6

6

20

40

6

6

6

80
200 400 800
Trajectory data length

Running time (sec)Running time (sec)

50

600
500
400
300
200
100

6

6

200

400

0

1600 3200

6
DB size

800

1600

図 2 The result on the running time (left) by varying the length

図 3 The result on the running time (left) by varying the DB sizeof trajectory data in database. Min-size is 3, min-length isof trajectory data in database. Min-size is 3, min-length is

12, max-width is 1. DB size is 100, pattern quantity is 6,

12, max-width is 1. Trajectory data length is 20, patternpattern size is 3, pattern width is 1, pattern length is 12,

quantity is 6, pattern size is 3, pattern width is 1, patternpattern start is 3.

length is 12, pattern start is 3.

4. Experiments

to examine basic properties of the proposed algorithm BEM
on trajectory data-set.
4. 1 Data and method
We used random trajectory data-set generated by Data
Generator . Data Generator is a program we made for validating and testing our algorithm. It generates trajectorydata as “x coordinate, y coordinate, time stamp” given byparameters of quantity, length, time interval of trajectorydata and the quantity, size, width, start, length of patterns

Running time (sec)

Finally, we report preliminary computational experiments

5.3
5.2
5.1
5
4.9
4.8
4.7
4.6
4.5
4.4
4.3
4.2

96

48

6

6

24

12

12

in trajectory data and the min-bound and max-bound of

24
Pattern quantity

48

96

random x and y coordinate of trajectory data. We set timeinterval is 1 second, min-bound is 1, and max-bound is 10
for all experiments. The following is an example of four lines
of one trajectory data file:

図 4 The result on the running time (left) by varying the patternquantity of trajectory data in database. Min-size is 3, minlength is 12, max-width is 1. Trajectory data length is 20,
DB size is 500, pattern size is 3, pattern width is 1, pattern

8.85633,6.80149,1

length is 12, pattern start is 2.

4.91046,3.70516,2

data length increases, and for every experiment, the algo-

5.2009,9.26173,3

rithm could find all 6 patterns included in database.

4.50338,3.21286,4

In Fig. 3 and Fig. 4, we show the result on the running...

time (left) by varying the size of database and quantity ofpatterns included in database. We observe that the run-All the lines in one file belong to one moving object.
We implemented our algorithm BEM in C++ and compiled by g++ of GNU, version 4.5.3. We used a PC (Intel
Core i7 CPU, 2.80GHz, 8GB of RAM) running Windows 7.

ning time increases as these two parameters increases, andfor every experiment, the algorithm could find all patterns
included in database.
In Fig. 6, Fig. ?? and Fig. 7, we show the results on the

4. 2 Results

running time (left) and the quantity of patterns found by our

In Fig. 2, we show the result on the running time (left)

algorithm (near the points) by varying the min-size, the max-by varying the length of trajectory data in database. We

width, and the min-length, respectively. In these figures, weobserved that the running time increases as the trajectory

35

8.65
6

8.6

Running time (sec)Running time (sec)

8.55
8.5
8.45
8.4
8.35

8.3 1494

222

978

312

30

258

25
222

20

150

15
10
5

8.25

6

0

8.2
2

4

Min-size

6

3

8

6

12
Min-length2448

図 5 The result on the running time (left) by varying the input of

図 7 The result on the running time (left) by varying the input ofmin-size. Min-length is 12, max-width is 1. Trajectory data

min-length. Max-width is 1, min-size is 3. Trajectory data

length is 20, DB size is 500, pattern size is 8, pattern quan-

length is 60, DB size is 500, pattern size is 3, pattern quan-tity is 6, pattern width is 1, pattern length is 12, patterntity is 6, pattern width is 1, pattern length is 48, pattern

start is 2.

start is 2.

14

839

12
Running time (sec)width θ, min-length ℓ, and min-frequency σ, finds all frequentenvelope patterns with width <= θ, length >= ℓ, and frequency>= σ in a trajectory database.

10
8
6

6

6

6

7

7

12

14

59

4
2

文

0
1

1.5

2

2.5
3
3.5
Max-width

4

4.5

5

図 6 The result on the running time (left) by varying the input of

max-width. Min-length is 12, min-size is 3. Trajectory data
length is 20, DB size is 500, pattern size is 3, pattern quantity is 6, pattern width is 1, pattern length is 12, pattern
start is 2.

first saw that the algorithm discovered the sub-patterns included in bigger longer ones.
Summary of Experiments: As it can be seen from the figures, our algorithm can find all patterns included in databasesuccessfully in Fig. 2, Fig. 3 and Fig. 4. But it also finds subpatterns in Fig. 6 and Fig. 7 when we input smaller min-sizeand shorter min-length. As the input parameters of minsize and max-width become larger in Fig. 6 and Fig. ??, theperformance of our algorithm turns bad obviously.

5. Conclusion
We presented an eﬃcient algorithm BEM that, given max-

献[1] V. Marcos, B. Petko, and V. Tsotras, “On-line discoveryof flock patterns in spatio-temporal data,” in Proc. ACM
GIS’09. ACM, 2009, pp. 286–295.
[2] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, “Trajectory pattern mining,” in Proc. KDD’07. ACM, 2007,
pp. 330–339.
[3] J. Hoyoung, L. Y. Man, Z. Xiaofang, J. Christian, and
S. HengTao, “Discovery of convoys in trajectory databases,”in Proc. PVLDB’08. VLDB Endowment, 2008.
[4] M. Benkert, J. Gudmundsson, F. Hubner, and T. Wolle,“Reporting flock patterns,” Computational Geometry,vol. 41, pp. 111–125, 2008.
[5] L. Zhenhui, D. Bolin, H. Jiawei, and K. Roland, “Swarm:
Mining relaxed temporal moving object clusters,” inProc. PVLDB’10. VLDB Endowment, 2010.
[6] K. Panos, M. Nikos, and B. Spiridon, “On discovering moving clusters in spatio-temporal data,” in Proc. SSTD’05,
ser. LNCS, vol. 3633. Springer-Verlag, 2005.