Database Reference
In-Depth Information
6.1.
Time and Accuracy Experiments
Here we present the results of some experiments using the approximation
algorithm to compute the similarity function
2. Our dataset here comes
from marine mammals' satellite tracking data
2
. It consists of sequences of
geographic locations of various marine animals (dolphins, sea lions, whales,
etc) tracked over different periods of time, that range from one to three
months (
SEALS
dataset). The length of the sequences is close to 100.
In Table 1 we show the computed similarity between a pair of sequences
in the
SEALS
dataset. We run the exact and the approximate algorithm
for different values of
S
K
is the number of times the approximate algorithm invokes the
LCSS
proce-
dure (that is, the number of translations
δ
and
ε
and we report here some indicative results.
that we try). As we can see using
only a few translation we get very good results. We got similar results for
synthetic datasets. Also, in Table 2 we report the running times to com-
pute the similarity measure between two sequences of the same dataset. The
approximation algorithm uses again from 15 to 60 different runs. The run-
ning time of the approximation algorithm is much faster even for
c
= 60.
As can be observed from the experimental results, the running times of
the approximation algorithm is not proportional to the number of runs (
K
).
This is achieved by reusing the results of previous translations and termi-
nating early the execution of the current translation, if it is not going to
yield a better result. The main conclusion of the above experiments is that
the approximation algorithm can provide a very tractable time vs accu-
racy trade-off for computing the similarity between two sequences, when
the similarity is defined using the
LCSS
model.
K
Table 1.
Similarity values between two sequences from our SEALS
dataset.
Similarity
Error(%)
for
K
=60
δ
E
Exact
Approximate for
K
tries
15
30
60
2
0.25
0.71134
0.65974
0.71134
0.696701
1.4639
2
0.5
0.907216
0.886598
0.893608
0.9
0.7216
4
0.25
0.71230
0.680619
0.700206
0.698041
1.2094
4
0.5
0.927835
0.908763
0.865979
0.922577
0.5258
6
0.25
0.72459
0.669072
0.698763
0.71134
1.325
6
0.5
0.938144
0.938
0.919794
0.92087
1.7274
2
http://whale.wheelock.edu/whalenet-stuff/stop cover.html
