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.
On Placing Skips Optimally In Expectation / Chierichetti, Flavio; Lattanzi, Silvio; Mari, Federico; Panconesi, Alessandro. - ELETTRONICO. - (2008), pp. 15-24. (Intervento presentato al convegno ACM International Conference on Web Search and Data Mining (WSDM 2008) tenutosi a Stanford, California, USA nel February 11-12, 2008) [10.1145/1341531.1341537].
On Placing Skips Optimally In Expectation.
CHIERICHETTI, FLAVIO;LATTANZI, SILVIO;MARI, FEDERICO;PANCONESI, Alessandro
2008
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
