Database Reference
In-Depth Information
Fig. 4. Solving the
LCSS
problem using dynamic programming. The gray area indicates
the elements that are examined if we confine our search window. The solution provided
is still the same.
3.2.
Extending the
LCSS
Model
Having seen that there exists an ecient way to compute the
LCSS
between
two sequences, we extend this notion in order to define a new, more flexible,
similarity measure. The
LCSS
model matches exact values, however in our
model we want to allow more flexible matching between two sequences,
when the values are within certain range. Moreover, in certain applications,
the stretching that is being provided by the
LCSS
algorithm needs only to
be within a certain range, too.
We assume that the measurements of the time-series are at fixed and
discrete time intervals. If this is not the case then we can use interpolation
[23,34].
Definition 3.
Givenaninteger
δ
and a real positive number
ε
, we define
the
LCSS
δ,ε
(
A, B
) as follows:
0 f
A
or
B
is empty
1+
LCSS
δ,ε
(Head(
A
)
,
Head(
B
))
LCSS
δ,ε
(
A, B
)=
if
|a
n
− b
n
| <ε
and
|n − m|≤δ
max(
LCSS
δ,ε
(Head(
A
)
,B
)
,LCSS
δ,ε
(
A,
Head(
B
)))
otherwise