Database Reference
In-Depth Information
approach for sequence similarity that is based on probabilistic matching,
using Hidden Markov Models. However the scalability properties of this
approach have not been investigated yet. A recent work that proposes a
method to cluster trajectory data is due to Gaffney and Smyth [17]. They
use a variation of the EM (expectation maximization) algorithm to cluster
small sets of trajectories. However, their method is a model based approach
that usually has scalability problems.
The most related paper to our work is the Bozkaya
et al.
[8]. They dis-
cuss how to define similarity measures for sequences of multidimensional
points using a restricted version of the edit distance which is equivalent to
the
LCCS
. Also, they present two ecient methods to index the sequences
for similarity retrieval. However, they focus on sequences of feature vectors
extracted from images and they do not discuss transformations or approx-
imate methods to compute the similarity.
Lately, there has been some work on indexing moving objects to answer
spatial proximity queries (range and nearest neighbor queries) [1,28,39].
Also, in [33], Pfoser
et al.
present index methods to answer topological
and navigational queries in a database that stores trajectories of moving
objects. However these works do not consider a global similarity model
between sequences but they concentrate on finding objects that are close to
query locations during a time instant, or time period that is also specified
by the query.
2.2.
Indexing Time Series
Indexing refers to the organization of data in such a way, so as not only to
group together similar items, but also to facilitate the pruning of irrelevant
data. The second part is greatly affected from the fact whether our distance
function is metric or not.
Definition 1.
A distance function
d
(
x, y
) between two objects
x
and
y
is
metric when it complies to the following properties:
1. Positivity,
d
(
x, y
)
≥
0and
d
(
x, y
)=0iff
x
=
y
.
2. Symmetry,
d
(
x, y
)=
d
(
y, x
).
3. Triangle Inequality,
d
(
x, y
)+
d
(
y, z
)
≥ d
(
x, z
).
Example:
The Euclidean distance
is
a metric distance function. The
pruning power of such a function can be shown in the following exam-
ple(Figure 3); Assume we have a set of sequences, including sequences
Seq
1
,
