Database Reference
In-Depth Information
1.1.
Terminology and Notation
A time sequence
x
=
x
1
=(
v
1
,t
1
)
,...,x
n
=(
v
n
,t
n
)
is an ordered col-
lection of elements
x
i
, each consisting of a value
v
i
and a timestamp
t
i
.
Abusing the notation slightly, the value of
x
i
.
For some retrieval methods, the values may be taken from a finite class
of values [Mannila and Ronkainen (1997)], or may have more than one
dimension [Lee
et al
. (2000)], but it is generally assumed that the values
are real numbers. This assumption is a requirement for most of the methods
described in this chapter.
The only requirement of the timestamps is that they be non-decreasing
(or, in some applications, strictly increasing) with respect to the sequence
indices:
x
i
may be referred to as
t
i
≤ t
j
⇔ i ≤ j.
(1)
In some methods, an additional assumption is that the elements are
equi-spaced
: for every two consecutive elements
x
i
and
x
i
+1
we have
t
i
+1
− t
i
=∆
,
(2)
where ∆ (the
sampling rate
of
) is a (positive) constant. If the actual
sampling rate is not important, ∆ may be normalized to 1, and
x
t
1
to 0. It
is also possible to resample the sequence to make the elements equi-spaced,
when required.
The
length
of a time sequence
x
is its cardinality, written as
|x|
.The
contiguous subsequence of
x
containing elements
x
i
to
x
j
(inclusive) is
x
i
:
j
.A
signature
of a sequence
x
written
is some structure that somehow
x
x
represents
. In the context of this chapter, such
a signature will always be a vector of fixed size
, yet is simpler than
. (For a more thorough
discussion of signatures, see Section 3.) Such a signature is written
k
x
.For
a summary of the notation, see Table 1.
Table 1.
Notation.
x
A sequence
x
A signature of
x
x
i
Element number
i
of
x
x
i
:
j
Elements
i
to
j
(inclusive) of
x
|
x
|
The length of
x