Wednesday, May 19, 2010

Postings list intersection with skip pointers

The list lengths are m and n. If we go through the two posting lists simultaneously, it takes O(m+n) operations. With skip pointers:

In following figure, when we reach “8” and move it to the result list, the next pointers are “16” and “41” in upper/lower list. Rather than simple advancing the upper pointer, we found the skip list pointer “28” is also less than “41”. Hence we can follow the skip list pointer and advance the upper pointer to “28”, thus avoid to “19,23”.


Now how many steps to skip? suggestion is sqrt(p), where p is the posting list length. The algorithm is:


No comments:

Post a Comment