Database Reference
In-Depth Information
(as before,
F
is the set of translations). Now we can show the following
lemma:
Lemma 4.
Given trajectories A,B,C:
LCSS
δ,
2
ε
(
A, C
)
>LCSS
δ,ε,F
(
A, B
)+
LCSS
δ,ε,F
(
B, C
)
−|B|
where
|B|
is the length of sequence B.
A
B
Proof:
Clearly, if an element of
canmatchanelementof
within
ε
B
C
ε
, and the same element of
matches an element of
within
,then
the element of
A
can also match the element of
C
within 2
ε
. Since there
are at least
|B|−
(
|B|−LCSS
δ,ε,F
(
A, B
))
−
(
|B|−LCSS
δ,ε,F
(
B, C
)) ele-
ments of
B
that match with elements of
A
andwithelementsof
C
,it
follows that
LCSS
δ,
2
ε,F
(
A, C
)
> |B|−
(
|B|−LCSS
δ,ε,F
(
A, B
))
−
(
|B|−
LCSS
δ,ε,F
(
B, C
)) =
LCSS
δ,ε,F
(
A, B
)+
LCSS
δ,ε,F
(
B, C
)
−|B|
.
5.1.
Indexing Structure
We first partition all the sequences into sets according to length, so that
the longest sequence in each set is at most
a
times the shortest (typically
we use
= 2.) We apply a hierarchical clustering algorithm on each set,
and we use the tree that the algorithm produced as follows:
For every node
a
M
C
)of
each cluster. The medoid is the sequence that has the minimum dis-
tance (or maximum
LCSS
) from every other sequence in the clus-
ter: max
vi∈C
min
vj∈C
LCSS
δ,ε,F
(
C
ofthe reewe torethemedoid(
v
i
,v
j
,e
). So given the tree and a query
Q
sequence
, we want to examine whether to follow the subtree that is
rooted at
C
. However, from the previous lemma we know that for any
sequence
B
in
C
:
LCSS
δ,ε,F
(
B, Q
)
< |B|
+
LCSS
δ,
2
ε,F
(
M
C
,Q
)
− LCSS
δ,ε,F
(
M
C
,B
)
or in terms of distance:
−
LCSS
δ,ε,F
(
B, Q
)
D
2(
δ, ε, B, Q
)=1
min(
|B|, |Q|
)
M
c
,Q
|B|
)
−
LCSS
δ,
2
ε,F
(
)
>
1
−
min(
|B|, |Q|
min(
|B|, |Q|
)
+
LCSS
δ,ε,F
(
M
c
,B
)
.
min(
|B|, |Q|
)
