On Placing Skips Optimally in Expectation
Chierichetti
Flavio
author
Lattanzi
Silvio
author
Mari
Federico
author
Panconesi
Alessandro
author
2008
Acm
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. The placement is optimal in the sense that it minimizes the expected time to process a query. Our theoretical results are matched by experiments with a real corpus, showing that substantial savings can be obtained with respect to the tra- ditional skip placement strategy, that of placing consecutive skips, each spanning sqrt(n) many locations.
Information Retrieval
exported from refbase (http://mclab.di.uniroma1.it/publications/show.php?record=94), last updated on Thu, 22 Nov 2012 14:59:18 +0100
text
http://mclab.di.uniroma1.it/publications/papers/papers/Chierichetti2008.pdf
10.1145/1341531.1341537
Chierichetti_etal2008
Sapienza @ mari @ ChiLatMar08
Web Search and Web Data Mining (WSDM 2008)
Najork
M.
editor
Broder
A.Z.
editor
Chakrabarti
S.
editor
2008
Acm
conference publication
15
24