Database Reference
In-Depth Information
i+1
e
i
s
i
e
i
s
i
e
i+1
s
t
s
t
e
i
s
i
e
t
s
t
e
t
s
t
e
overlap
i+1 precedes t
i and t form closest pair
Fig. 3.
Some possibilities when
i
e
<t
e
if
i
+1
e
≤
t
e
then
make
i
+1
the new
initiator
, and re-process the new
initiator
and
terminator
else
this means
initiator
completely precedes
terminator
, without any overlap, and
there is no other tuple from the
initiator
set occurring before
terminator
.Now,
check if the distance criterion is satisfied.
if
(
t
s
-
i
e
)
d
then
combine
initiator
and
terminator
advance
initiator
and
terminator
else
does not satisfy distance
lookahead
to determine new
initiator
and
terminator
, re-process them
Case 2
(
i
e
==
t
e
): This means
initiator
and
terminator
overlap (they have the same
end offset). Perform a lookahead, and re-process.
Case 3
(
i
e
>t
e
): This means our assumption of
initiator
and
terminator
is wrong.
The terminator precedes the initiator, either in an overlapping fashion, or a non-
overlapping fashion as shown in Figure 4. In this case, we swap the
≤
initiator
and
terminator
pointers, and re-process.
t
s
t
e
t
s
t
e
i
s
i
e
i
s
i
e
no overlap
overlap
Fig. 4.
Some possibilities when
t
e
<i
e
Lookahead algorithm:
A lookahead is done when the current
initiator
and
terminator
cannot be combined due to an overlap, or because the distance criterion
is not satisfied. At this point, we cannot determine which one from
initiator
and
terminator
to keep, and which one to discard. We look ahead one tuple from both
sets, and assign the one that occurs first as the new terminator. The older tuple from the
