How should we place skip pointers (heuristics)?

shorter skip spans -> more likely to skip. However, more comparisons as well.

Fewer skips -> less likely to skip, but less comparisons!

What is the line we can draw?


For postings of length L, use \(\sqrt{L}\) evenly-spaced skip pointers.

This ignores the distribution of query terms.

Easy if the index is relatively static. Harder if L is variable length.