TABLE OF CONTENTS To compute the similarity functions S1 we have to runa LCSS computation for the two sequences. The LCSS can be computed by a dynamic programming algorithm in O ( n* m) time. However we only allow matchings when the difference in the indices is at most ?, and this allows the use of a faster algorithm. The following lemma has been shown in [12].
Given two sequences A and B, with A = n and B = m, we can find the LCSS ?,?( A, B) in O ( ?( n + m)) time.
If ? is small, the dynamic programming algorithm is very efficient. However, for some applications ? may need to be large. In this case, we can speed-up the above computation using random sampling. Given two sequences A and B, we compute two subsets RA and RB by sampling each sequence. Then we use the dynamic programming algorithm to compute the LCSS on RA and RB. We can show that, with high probability, the result of the algorithm over the samples, is a good approximation of the actual value. We describe this technique in detail in [40].
We now consider the more...
