Database Reference
In-Depth Information
2. An ecient indexing scheme, which will speed up the user queries.
We will briefly discuss some issues associated with these two topics.
2.1.
Time Series Similarity Measures
The simplest approach to define the distance between two sequences is to
map each sequence into a vector and then use a p-norm to calculate their
distance. The p-norm distance between two n-dimensional vectors
x
and
y
is defined as:
)=
n
p
|x
i
− y
i
|
p
L
p
(
x, y
i
=1
For
p
= 2 it is the well known Euclidean distance and for
p
=1the
Manhattan distance.
Most of the related work on time-series has concentrated on the use of
some metric
L
p
Norm. The advantage of this simple model is that it allows
ecient indexing by a dimensionality reduction technique [2,15,19,44]. On
the other hand the model cannot deal well with outliers and is very sensi-
tive to small distortions in the time axis. There are a number of interesting
extensions to the above model to support various transformations such as
scaling [10,36], shifting [10,21], normalization [21] and moving average [36].
Other recent works on indexing time series data for similarity queries assum-
ing the Euclidean model include [25,26]. A domain independent framework
for defining queries in terms of similarity of objects is presented in [24].
In [29], Lee
et al.
propose methods to index sequences of multidimensional
points. The similarity model is based on the Euclidean distance and they
extend the ideas presented by Faloutsos
et al.
in [16], by computing the
distances between multidimensional Minimum Bounding Rectangles.
Another, more flexible way to describe similar but out-of-phase
sequences can be achieved by using the
Dynamic Time Warping (DTW)
[38]. Berndt and Clifford [5] were the first that introduced this measure in
the datamining community. Recent works on
DTW
are [27,31,45].
DTW
has
been first used to match signals in speech recognition [38].
DTW
between
two sequences
A
and
B
is described by the following equation:
DTW
(
A, B
)=
D
base
(
a
m
,b
n
)+min
{
DTW
(Head(
A
)
,
Head(
B
))
,
A
,B
,
A,
B
}
DTW
(Head(
)
)
DTW
(
Head(
))
where
D
base
is some
L
p
Norm and Head(
A
) of a sequence
A
are all the
elements of
A
except for
a
m
,thelastone.
