Macdonald C., Ounis I., Tonellotto N. Upper-bound approximations for dynamic pruning. In: ACM Transactions on Information Systems, vol. 29 (4) article n. 17. ACM, 2011. |

Abstract (English) |
Dynamic pruning strategies for information retrieval systems can increase querying efﬁciency without decreasing effectiveness by using upper bounds to safely omit scoring documents that are unlikely to make the ﬁnal retrieved set. Often, such upper bounds are pre-calculated at indexing time for a given weighting model. However, this precludes changing, adapting or training the weighting model without recalculating the upper bounds. Instead, upper bounds should be approximated at querying time from various statistics of each term to allow on-the-ﬂy adaptation of the applied retrieval strategy. This article, by using uniform notation, formulates the problem of determining a term upper-bound given a weighting model and discusses the limitations of existing approximations. Moreover, we propose an upper-bound approximation using a constrained nonlinear maximization problem. We prove that our proposed upper-bound approximation does not impact the retrieval effectiveness of several modern weighting models from various different families. We also show the applicability of the approximation for the Markov Random Field proximity model. Finally, we empirically examine how the accuracy of the upper-bound approximation impacts the number of postings scored and the resulting efﬁciency in the context of several large Web test collections. | |

URL: | http://dl.acm.org/citation.cfm?id=2037662 | |

DOI: | 10.1145/2037661.2037662 | |

Subject | Performance Experimentation H.3.3 Information Search and Retrieval |

1) Download Document PDF |

Open access Restricted Private