Database Reference
In-Depth Information
3. Similarity Measures Based on
LCSS
3.1.
Original Notion of
LCSS
Suppose that we have two time series
A
=(
a
1
,a
2
,...,a
n
)and
B
=
(
b
1
,b
2
,...,b
m
). For
A
let Head(
A
)=(
a
1
,a
2
,...,a
n−
1
). Similarly, for
B
.
Definition 2.
The
LCSS
between
A
and
B
is defined as follows:
0
if
A
or
B
empty
,
1+
LCSS
(Head(
A
)
,B
))
if
a
n
=
b
n
,
LCSS
(
A, B
)=
max(
LCSS
(Head(
A
)
,B
)
,
otherwise
.
LCSS
(
A, Head
(
B
)))
The above definition is recursive and would require exponential time to
compute. However, there is a better solution that can be offered in
m
∗
n
O
(
)
time, using dynamic programming.
Dynamic Programming Solution [11,42]
The
LCSS
problem can easily be solved in quadratic time and space. The
basic idea behind this solution lies in the fact that the problem of the
sequence matching can be dissected in smaller problems, which can be com-
bined after they are solved optimally. So, what we have to do is, solve a
smaller instance of the problem (with fewer points) and then continue by
adding new points to our sequence and modify accordingly the
LCSS
.
Now the solution can be found by solving the following equation using
dynamic programming (Figure 4):
0
if
i
=0
,
0
if
j
=0
,
LCSS
[
i, j
]=
1+
LCSS
[
i −
1
,j −
1]
if
a
i
=
b
i
,
max(
LCSS
[
i −
1
,j
]
,LCSS
[
i, j −
1])
otherwise
.
where
LCSS
[
i, j
] denotes the longest common subsequence between the first
i
elements of sequence
A
and the first
j
elements of sequence
B
. Finally,
LCSS
[
] will give us the length of the longest common subsequence
between the two sequences
n, m
.
The same dynamic programming technique can be employed in order to
find the Warping Distance between two sequences.
A
and
B
