Database Reference
In-Depth Information
two trajectories is to use p-norm distance. The p-norm distance between trajectories
of
R
and
S
is defined as:
n
s
i
)
p
1
p
L
p
(
R
,
S
)
=
(
r
i
−
.
i
=
1
The p-norm distance requires the trajectory length to be the same, i.e.,
n
m
. The
well-known Euclidean distance and Manhattan distance are p-norm distance when
p
=
1 respectively.
The p-norm distance is easy to compute, but is sensitive to the time shift. Dynamic
Time Warping (DTW) [
39
] can handle the local time shifting and it does not need
the trajectories to be the same length. DTW is defined as:
=
2 and
p
=
⎛
⎞
DT W
(
R
[2 :
n
],
S
[2 :
m
]),
DT W
(
R
[2 :
n
],
S
),
DT W
(
R
,
S
[2 :
m
])
⎝
⎠
.
DT W
(
R
,
S
)
=
dist
(
r
1
,
s
1
)
+
min
Edit distance with Real Penalty (ERP) [
4
] introduces a constant value
g
as the
gap of edit distance and uses real distance between elements as the penalty to handle
local time shifting. ERP is defined as:
⎛
⎞
ERP
(
R
[2 :
n
],
S
[2 :
m
])
+
dist
(
r
1
,
s
1
),
⎝
⎠
.
ERP
(
R
,
S
)
=
min
ERP
(
R
[2 :
n
],
S
)
+
dist
(
r
1
,
g
),
ERP
(
R
,
S
[2 :
m
])
+
dist
(
s
1
,
g
)
The Longest Common Subsequences (LCSS) [
37
] requires a threshold
to be
established. The threshold is used to determine whether or not two elements match
and it allows LCSS to handle noise by quantizing the distance between two elements
to two values, 0 and 1, to remove the larger distance effects caused by noise. LCSS
is defined as:
LCSS
(
R
[2,
n
],
S
[2,
m
])
+
≤
dist
(
r
1
,
s
1
)
dist
(
r
1
,
s
1
)
LCSS
(
R
,
S
)
=
{
}
max
LCSS
(
R
[2,
n
],
S
),
LCSS
(
R
,
S
[2,
m
])
otherwise
Edit Distance on Real sequence (EDR) is defined similar to LCSS except EDR
assigns penalties to the gaps between two matched sub-trajectories according to the
lengths of gaps. EDR is defined as:
⎛
⎞
EDR
(
R
[2 :
n
],
S
[2 :
m
])
+
subcost
,
⎝
⎠
,
EDR
(
R
,
S
)
=
min
EDR
(
R
[2 :
n
],
S
)
+
1,
EDR
(
R
,
S
[2 :
m
]
+
1
=
≤
=
where
subcost
1 otherwise.
A comparison of the similarity measures is shown in Table
12.2
. All the measures
except Euclidean distance can handle local time shifting. And only Euclidean distance
requires the lengths of two trajectories to be the same. LCSS and EDR are more robust
0if
dist
(
r
1
,
s
1
)
and
subcost
