Database Reference
In-Depth Information
Methods exist for finding signatures of arbitrary objects, given the dis-
tances between them [Faloutsos and Lin (1995), Wang
et al
. (1999)], but
in the following I will concentrate on methods that exploit the structure of
the time series to achieve good approximations.
3.1.
A Simple Example
As an example of the signature based scheme, consider the two sequences
showninFigure4.
The sequences,
L
1
measure (Manhattan
distance), which is simply the sum of the absolute distances between each
aligning pair of values. A simple signature in this scheme is the prefix of
length 2, as indicated by the shaded area in the figure. As shown in Figure 5,
these signatures may be interpreted as points in a two-dimensional plane,
which can be indexed with some standard spatial indexing method. It is
also clear that the signature distance will underestimate the real distance
between the sequences, since the remaining summands of the real distance
must all be positive.
x
and
y
, are compared using the
Fig. 4.
Comparing two sequences.
Fig. 5.
A simple signature distance.
