Database Reference
In-Depth Information
EXTENDED-LEGS
The input is the list of legs in a series; the output is a list of all extended
legs.
initialize an empty stack
S
of leg indices
PUSH(
S,
1)
for
k
=2
to
l
do
while
S
is not empty and
ir
TOP(S)
<ir
k
do
next
[TOP(
S
)] = k; POP(
S
)
PUSH(
k
)
while
S
is not empty
do
next
[TOP(
S
)] = NIL; POP(
S
)
initialize an empty list of extended legs
for
k
=
1to
l −
1do
m
=
next
[
k
]
while
m
is not NIL
do
add (
il
k
,ir
m
) to the list of extended legs
m
=
next
[
m
]
Fig. 13.
Identifying extended legs. We assume that normal legs are numbered 1 to
l.
number of normal legs, and the time of the second part is linear in the
number of extended legs.
To evaluate the retrieval accuracy, we have compared the retrieval
results with the matches identified by a slow exhaustive search. We have
ranked the matches found by the retrieval algorithm from most to least
similar. In Figures 14 and 15, we plot the ranks of matches found by the
fast algorithm versus the ranks of exhaustive-search matches. For instance,
if the fast algorithm has found only three among seven closest matches, the
graph includes the point (3, 7). Note that the fast algorithm never returns
“false positives” since it verifies each candidate match.
The retrieval time grows linearly with the pattern length and with the
number of candidate segments identified at the initial step of the retrieval
algorithm. If we increase
the procedure finds more candidates and
misses fewer matchers, but the retrieval takes more time. In Table 5, we give
the mean number of candidate segments in the retrieval experiments, for
three different values of
C
and
D,
C
and
D
; note that this number does not depend
on the pattern length.
We have measured the speed of a Visual-Basic implementation on a 300-
MHz PC. If the pattern has
m
legs, and the procedure identifies
k
candidate
matches, then the retrieval time is 70
· m · k
microseconds. For the stock
