Searching for Complex Patterns over Large Stored Information Repositories - Advances in Databases - page 77

opposite set becomes the new initiator . Three possibilities exist when we consider the
lookahead tuples:
Case I ( i +1 e <t +1 e ): This means the next tuple in the initiator set occurs before the
next tuple in the terminator set. (We assume they belong to the same docID).
Make old terminator the new initiator
Make i +1 the new terminator

Case II ( i +1 e == t +1 e ): This means the next tuples have the same end offset. In this
case, we look at the older pair, and keep the one that occurs later as the new initiator .
if i e <t e then
Make old terminator the new initiator
Make i +1

the new terminator

else
This means initiator and terminator have the same end offset
Keep the initiator
Make t +1

the new terminator
Case III ( i +1 e >t +1 e ):
Keep the initiator
Make t +1 the new terminator

D1 <21, 40>
D2 <12, 24>
D3 <12, 47>

NEAR/
30

D1 <10, 18>
D1 <21, 25>
D2 <12, 18>
D2 <30, 35>
D3 <40, 47>
D4 <60, 80>
.
.

D1 <28, 40>
D2 <15, 20>
D2 <21, 24>
D3 <12, 19>
D4 <12, 20>
.
.

Fig. 5. Example of the NEAR operator algorithm

Figure 5 shows an example of the working of the NEAR operator. To begin, initia-
tor points to D1 < 10, 18 > in the left set, and terminator points to D1 < 28, 40 > in the
right set. Since the next tuple in the initiator set lies completely before terminator ,itis
assigned as the new initiator ( initiator is advanced). Now, initiator and terminator point
to a proximal pair of tuples, and hence they are merged and added to the output set as the
tuple D1 < 21, 40 > .When initiator and terminator point to D2 < 12, 18 > and D2 < 15,