{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T19:28:22Z","timestamp":1771702102275,"version":"3.50.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["EU-FP7-215483"],"award-info":[{"award-number":["EU-FP7-215483"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ASSETS","award":["CIP-ICT-PSP-250527"],"award-info":[{"award-number":["CIP-ICT-PSP-250527"]}]},{"name":"VISITO Tuscany","award":["POR-FESR-63748"],"award-info":[{"award-number":["POR-FESR-63748"]}]},{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"publisher","award":["TG090399"],"award-info":[{"award-number":["TG090399"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>Dynamic pruning strategies for information retrieval systems can increase querying efficiency without decreasing effectiveness by using upper bounds to safely omit scoring documents that are unlikely to make the final 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-fly 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 efficiency in the context of several large Web test collections.<\/jats:p>","DOI":"10.1145\/2037661.2037662","type":"journal-article","created":{"date-parts":[[2011,12,6]],"date-time":"2011-12-06T19:05:23Z","timestamp":1323198323000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Upper-bound approximations for dynamic pruning"],"prefix":"10.1145","volume":"29","author":[{"given":"Craig","family":"Macdonald","sequence":"first","affiliation":[{"name":"University of Glasgow, Scotland, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iadh","family":"Ounis","sequence":"additional","affiliation":[{"name":"University of Glasgow, Scotland, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Tonellotto","sequence":"additional","affiliation":[{"name":"Information Science and Technologies Institute, National Research Council of Italy (ISTI-CNR), Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646273"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11735106_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060784"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148235"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1571941.1572140"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956944"},{"key":"e_1_2_1_8_1","volume-title":"The TREC 2006 Terabyte track. In Proceedings of the 15th Text Retrieval Conference. E. M. Voorhees and L. P. Buckland, Eds. NIST","author":"Buttcher S.","unstructured":"Buttcher , S. , Clarke , C. L. A. , and Soboroff , I . 2007 . The TREC 2006 Terabyte track. In Proceedings of the 15th Text Retrieval Conference. E. M. Voorhees and L. P. Buckland, Eds. NIST , Gaithersburg, MD. Buttcher, S., Clarke, C. L. A., and Soboroff, I. 2007. The TREC 2006 Terabyte track. In Proceedings of the 15th Text Retrieval Conference. E. M. Voorhees and L. P. Buckland, Eds. NIST, Gaithersburg, MD."},{"key":"e_1_2_1_9_1","volume-title":"Overview of the TREC 2009 Web track. In Proceedings of the 18th Text Retrieval Conference. E. M. Voorhees and L. P. Buckland, Eds. NIST.","author":"Clarke C. L.","unstructured":"Clarke , C. L. , Craswell , N. , and Soboroff , I . 2010 . Overview of the TREC 2009 Web track. In Proceedings of the 18th Text Retrieval Conference. E. M. Voorhees and L. P. Buckland, Eds. NIST. Clarke, C. L., Craswell, N., and Soboroff, I. 2010. Overview of the TREC 2009 Web track. In Proceedings of the 18th Text Retrieval Conference. E. M. Voorhees and L. P. Buckland, Eds. NIST."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 33rd European Conference on IR Research: Advancesin Information Retrieval. P. Clough, C. Foley, C. Gurrin, G. J. Jones, W. Kraaij, H. Lee, and V. Murdoch, Eds. Springer","author":"Craswell N.","unstructured":"Craswell , N. , Fetterly , D. , and Najork , M . 2011. The power of peers . In Proceedings of the 33rd European Conference on IR Research: Advancesin Information Retrieval. P. Clough, C. Foley, C. Gurrin, G. J. Jones, W. Kraaij, H. Lee, and V. Murdoch, Eds. Springer , Berlin, Germany. Craswell, N., Fetterly, D., and Najork, M. 2011. The power of peers. In Proceedings of the 33rd European Conference on IR Research: Advancesin Information Retrieval. P. Clough, C. Foley, C. Gurrin, G. J. Jones, W. Kraaij, H. Lee, and V. Murdoch, Eds. Springer, Berlin, Germany."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Web Search Click Data Workshop at WSDM'09","author":"Craswell N.","unstructured":"Craswell , N. , Jones , R. , Dupret , G. , and Viegas , E. Eds . 2009 . In Proceedings of the Web Search Click Data Workshop at WSDM'09 . ACM Press, New York, NY. Craswell, N., Jones, R., Dupret, G., and Viegas, E. Eds. 2009. In Proceedings of the Web Search Click Data Workshop at WSDM'09. ACM Press, New York, NY."},{"key":"e_1_2_1_12_1","unstructured":"Croft W. B. Metzler D. and Strohman T. 2009. Search Engines\u2014Information Retrieval in Practice. Addison-Wesley Reading MA.   Croft W. B. Metzler D. and Strohman T. 2009. Search Engines\u2014Information Retrieval in Practice. Addison-Wesley Reading MA."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008992.1009004"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390356"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 7th International Conference on Computer-Assisted Information Retrieval. C. Fluhr, G. Grefenstette, and W. B. Croft, Eds. CID, 706--719","author":"He B.","unstructured":"He , B. and Ounis , I . 2004. A query-based pre-retrieval model selection approach to information retrieval . In Proceedings of the 7th International Conference on Computer-Assisted Information Retrieval. C. Fluhr, G. Grefenstette, and W. B. Croft, Eds. CID, 706--719 . He, B. and Ounis, I. 2004. A query-based pre-retrieval model selection approach to information retrieval. In Proceedings of the 7th International Conference on Computer-Assisted Information Retrieval. C. Fluhr, G. Grefenstette, and W. B. Croft, Eds. CID, 706--719."},{"key":"e_1_2_1_17_1","unstructured":"Jongen H. T. Meer K. and Triesch E. 2004. Optim. Theo. Springer Berlin Germany.  Jongen H. T. Meer K. and Triesch E. 2004. Optim. Theo. Springer Berlin Germany."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/860435.860449"},{"key":"e_1_2_1_19_1","volume-title":"Rank Correlation Methods","author":"Kendall M. G.","unstructured":"Kendall , M. G. 1955. Rank Correlation Methods 2 nd Ed. Charles Griffin & Company Limited , London, UK . Kendall, M. G. 1955. Rank Correlation Methods 2nd Ed. Charles Griffin & Company Limited, London, UK.","edition":"2"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Efficiency Issues in Information Retrieval Workshop at ECIR. R. Blanco and F. Silvestri, Eds.","author":"Lacour P.","unstructured":"Lacour , P. , Macdonald , C. , and Ounis , I . 2008. Efficiency comparison of document matching techniques . In Proceedings of the Efficiency Issues in Information Retrieval Workshop at ECIR. R. Blanco and F. Silvestri, Eds. Lacour, P., Macdonald, C., and Ounis, I. 2008. Efficiency comparison of document matching techniques. In Proceedings of the Efficiency Issues in Information Retrieval Workshop at ECIR. R. Blanco and F. Silvestri, Eds."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646288"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1561\/1500000016"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of Web N-gram 2010 Workshop at SIGIR. C. Zhai, D. Yarowsky, E. Viegas, K. Wang, and S. Vogel, Eds.","author":"Macdonald C.","unstructured":"Macdonald , C. and Ounis , I . 2010. Global statistics in proximity weighting models . In Proceedings of Web N-gram 2010 Workshop at SIGIR. C. Zhai, D. Yarowsky, E. Viegas, K. Wang, and S. Vogel, Eds. Macdonald, C. and Ounis, I. 2010. Global statistics in proximity weighting models. In Proceedings of Web N-gram 2010 Workshop at SIGIR. C. Zhai, D. Yarowsky, E. Viegas, K. Wang, and S. Vogel, Eds."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076115"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/237496.237497"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344411.1344415"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/188490.188597"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 1st Text REtrieval Conference. D. K. Harman, Ed. NIST Special Publication","volume":"207","author":"Robertson S. E.","unstructured":"Robertson , S. E. , Walker , S. , Hancock-Beaulieu , M. , Gull , A. , and Lau , M . 1992. Okapi at TREC . In Proceedings of the 1st Text REtrieval Conference. D. K. Harman, Ed. NIST Special Publication , vol. 500- 207 . NIST. Robertson, S. E., Walker, S., Hancock-Beaulieu, M., Gull, A., and Lau, M. 1992. Okapi at TREC. In Proceedings of the 1st Text REtrieval Conference. D. K. Harman, Ed. NIST Special Publication, vol. 500-207. NIST."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of String Processing and Information Retrieval. N. Ziviani and R. A. Baeza-Yates, Eds. Springer","author":"Schenkel R.","unstructured":"Schenkel , R. , Broschart , A. , Hwang , S. , Theobald , M. , and Gatford , M . 2007. Efficient text proximity search . In Proceedings of String Processing and Information Retrieval. N. Ziviani and R. A. Baeza-Yates, Eds. Springer , Berlin, Germany, 287--299. Schenkel, R., Broschart, A., Hwang, S., Theobald, M., and Gatford, M. 2007. Efficient text proximity search. In Proceedings of String Processing and Information Retrieval. N. Ziviani and R. A. Baeza-Yates, Eds. Springer, Berlin, Germany, 287--299."},{"key":"e_1_2_1_30_1","unstructured":"Silverstein C. Henzinger M. Marais H. and Moricz M. 1998. Analysis of a very large AltaVista query log. Tech. rep. 1998-014. Digital SRC Palo Alto CA.  Silverstein C. Henzinger M. Marais H. and Moricz M. 1998. Analysis of a very large AltaVista query log. Tech. rep. 1998-014. Digital SRC Palo Alto CA."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390359"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183698"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 8th Workshop on Large-Scale Distributed Systems for Information Retrieval at SIGIR. R. Blanco, B. B. Cambazoglu, and C. Lucchese, Eds. CEUR Workshop Proceedings","volume":"630","author":"Tonellotto N.","unstructured":"Tonellotto , N. , Macdonald , C. , and Ounis , I . 2010. Efficient dynamic pruning with proximity support . In Proceedings of the 8th Workshop on Large-Scale Distributed Systems for Information Retrieval at SIGIR. R. Blanco, B. B. Cambazoglu, and C. Lucchese, Eds. CEUR Workshop Proceedings , vol. 630 . Tonellotto, N., Macdonald, C., and Ounis, I. 2010. Efficient dynamic pruning with proximity support. In Proceedings of the 8th Workshop on Large-Scale Distributed Systems for Information Retrieval at SIGIR. R. Blanco, B. B. Cambazoglu, and C. Lucchese, Eds. CEUR Workshop Proceedings, vol. 630."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(95)00020-H"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835449.1835525"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/984321.984322"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321547"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458174"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646255"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2037661.2037662","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2037661.2037662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:28Z","timestamp":1750240468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2037661.2037662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2037661.2037662"],"URL":"https:\/\/doi.org\/10.1145\/2037661.2037662","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2010-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}