TABLE OF CONTENTS In this section we show how to use the hierarchical tree of a clustering algorithm in order to efficiently answer nearest neighbor queries in a dataset of sequences.
The distance function D2 is not a metric because it does not obey the triangle inequality. This makes the use of traditional indexing techniques difficult. An example is shown in Figure 12, where we observe that LCSS( ?, ?, A, B) = 1 and LCSS( ?, ?, B, C) = 1, therefore the respective distances are both zero. However, obviously D2( ?, ?, A, C) > D2( ?, ?, A, B) + D2( ?, ?, B, C) = 0 + 0.
We can however prove a weaker version of the triangle inequality, which can help us avoid examining a large portion of the database objects. First we define:
Clearly,
(as before, F is the set of translations). Now we can show the following lemma:
Given trajectories A, B, C:
where B is the length of sequence B.
| Proof | Clearly, if an element of A can match an element of B within ?, and the same element of B matches an element of C |
