Database Reference
In-Depth Information
day 1
y
10
day 1
y
day 2
day 3
day 2
day 3
10
A
O
I
N
C
J
5
5
B
H
events sequence:
M
A A C C C G | A A C B D G | A A A C H G
D
L
G
some partial periodic patterns:
E
F
K
support(AA***G) = 3
support(AAC**G) = 2
x
x
support(AA*C*G) = 2
5
10
5
10
a
b
c
am object's movement
a set of predefined regious
event-based patterns
Fig. 12.3
Periodic patterns with respect to pre-defined spatial regions [
28
]
T
, the timeline are segmented by length
T
and the observations are mapped to a rela-
tive timescale [1,
T
]. If
T
is the true period, the observations will show highly skewed
distributions of the observations. Otherwise, the observations will be scattered over
[1,
T
].
3.2
Frequent Periodic Pattern Mining
Given the period, such as a day or a week, we are interested in mining the frequent
regular trajectory patterns. For example, people wake up at the same time and follow
more or less the same route to their work everyday. The discovery of hidden periodic
patterns in spatiotemporal data, apart from unveiling important information to the
data analyst, can facilitate data management substantially.
The key challenge to mine frequent pattern in movement lies in how to
transform a
2-dimensional movement sequence to 1-dimensional symbolic sequence
. As proposed
by Mamoulis et al. [
28
], one way to handle this issue is to replace the exact locations
by the regions (e.g., districts, cellphone towers, or cells of a synthetic grid) which
contain them. Figure
12.3
b shows an example of an area's division into such regions.
By using the regions, we can transform a raw movement sequence as shown in
Fig.
12.3
a to an event sequence as shown in Fig.
12.3
c. Now the problem becomes a
traditional frequent periodic pattern mining problem [
16
]. In real scenario, sometimes
we are interested in the
automated
discovering of descriptive regions. Mamoulis et
al. [
28
] further propose to cluster the locations at corresponding relative timestamps,
such as clustering locations at 10am over different days. They propose a top-down
pattern mining method, which is more efficient than typical bottom-up method.
3.3
Using Periodic Pattern for Location Prediction
One important application of frequent periodic pattern is for future location predic-
tion. For example, if a person repeats his periodic pattern between home and office
every weekday, we could predict that this person is very likely to be in the office at
