Search for question
Question

3. We have a two-word query. For one term the postings list consists of the following 16

entries:

[4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180]

and for the other it is the one entry postings list:

[47].

Work out how many comparisons would be done to intersect the two postings lists with

the following two strategies. Briefly justify your answers (Let (x,y) denote a posting

comparison. x refers to a value in the upper list and y refers to a value in the lower list)

write down those comparisons):

a. Using standard postings lists

b. Using postings lists stored with skip pointers, with a skip length of VP (for a postings

list of length P).

Fig: 1