Exercise

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:

Using standard postings lists

Using postings lists stored with skip pointers, with a skip length of $\sqrt[\phantom{2}]{P},$