Database Reference
In-Depth Information
pattern
Fig. 11.
Example of retrieved stock charts.
(a) Prominent
leg of a pattern.
(b) Dissimilar legs.
(c) Extended legs.
Fig. 12. Example of extended legs. The pattern (a) matches the series (b), but the
pattern's prominent leg has no equivalent in the series. If we identify the extended legs
(c), the prominent leg matches one of them.
The described procedure can miss a matching segment that does not
have a leg corresponding to the pattern's prominent leg. We illustrate
this problem in Figure 12, where the prominent leg of the pattern has no
equivalent in the matching series. To avoid this problem, we introduce the
notion of an
extended leg,
which is a segment that would be a leg under a
higher compression rate (Figure 12c). Formally, points
a
i
and
a
j
of a series
a
1
,...,a
n
form an extended upward leg if
• a
i
is a local minimum, and
a
j
is a local maximum, and
•
m ∈
i, j
,
a
i
<a
m
<a
j
.
for every
[
]
we have
The definition of an extended downward leg is similar.
We identify all extended legs, and index them in the same way as nor-
mal legs. The advantage of this approach is more accurate retrieval, and
the disadvantage is a larger indexing structure. In Figure 13, we give an
algorithm for identifying upward extended legs; the procedure for finding
downward extended legs is similar. We assume that normal upward legs in
the input series are numbered from 1 to
l.
First, the procedure processes
important maxima; for each maximum
ir
k
,
it identifies the
next larger
max-
imum and stores its index in
Second, it uses this information to
identify extended legs. The running time of the first part is linear in the
next
[
k
]
.
