On placing skips optimally in expectation
Flavio Chierichetti, Silvio Lattanzi, Federico Mari, Alessandro Panconesi · 2008
We study the problem of optimal skip placement in an inverted list. Assuming the query distribution to be known in advance, we formally prove that an optimal skip placement can be computed quite efficiently. Our best algorithm runs in time O (n log n), n being the length of the list.