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?
Heuristic
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.