Conference article  Open Access

Upper bound approximations for BlockMaxWand

Macdonald C., Tonellotto N.

BlockMaxWand  Wand  Upper-bounds approximations 

BlockMaxWand is a recent advance on the Wand dynamic pruning technique, which allows efficient retrieval without any e.ectiveness degradation to rank K. However, while BMW uses docid-sorted indices, it relies on recording the upper bound of the term weighting model scores for each block of postings in the inverted index. Such a requirement can be disadvantageous in situations such as when an index must be updated. In this work, we examine the appropriateness of upper-bound approximation - which have previously been shown suitable for Wand- in providing efficient retrieval for BMW. Experiments on the ClueWeb12 category B13 corpus using 5000 queries from a real search engine's query log demonstrate that BMW still provides benefits w.r.t. Wand when approximate upper bounds are used, and that, if approximations on upper bounds are tight, BMW with approximate upper bounds can provide eficiency gains w.r.t. Wand with exact upper bounds, in particular for queries of short to medium length.

Source: ICTIR 2017 - 3rd ACM International Conference on the Theory of Information Retrieval, pp. 273–276, Amsterdam, The Netherlands, 1-4 October, 2017

[1] Andrei Z. Broder, David Carmel, Michael Herscovici, Aya So‚er, and Jason Y. Zien. 2003. Ecient query evaluation using a two-level retrieval process. In CIKM. 426-434.
[2] Ma‹ Crane, J. Shane Culpepper, Jimmy Lin, Joel Mackenzie, and Andrew Trotman. 2017. A Comparison of Document-at-a-Time and Score-at-a-Time ery Evaluation. In WSDM. 201-210.
[3] Nick Craswell, Rosie Jones, Georges Dupret, and Evelyne Viegas (Eds.). 2009. Proceedings of the Web Search Click Data Workshop at WSDM 2009.
[4] Je‚rey Dean. 2009. Challenges in building large-scale information retrieval systems: invited talk. In WSDM.
[5] Constantinos Dimopoulos, Sergey Nepomnyachiy, and Torsten Suel. 2013. Optimizing Top-k Document Retrieval Strategies for Block-max Indexes. In WSDM. 113-122.
[6] Shuai Ding and Torsten Suel. 2011. Faster top-k document retrieval using blockmax indexes. In SIGIR. 993-1002.
[7] Hui Fang, Tao Tao, and ChengXiang Zhai. 2004. A Formal Study of Information Retrieval Heuristics. In SIGIR. 49-56.
[8] Craig Macdonald, Iadh Ounis, and Nicola Tonello‹o. 2011. Upper-bound Approximations for Dynamic Pruning. ACM Trans. Inf. Syst. 29, 4 (2011), 17:1-17:28.
[9] Iadh Ounis, Gianni Amati, Vassilis Plachouras, Ben He, Craig Macdonald, and Christina Lioma. 2006. Terrier: A High Performance and Scalable IR Platform. In OSIR.
[10] Ma‹hias Petri, J. Shane Culpepper, and Alistair Mo‚at. 2013. Exploring the Magic of WAND. In ADCS. 58-65.
[11] Sebastiano Vigna. 2013. asi-succinct indices. In WSDM. 83-92.
[12] Lidan Wang, Jimmy Lin, and Donald Metzler. 2010. Learning to Eciently Rank. In SIGIR. 138-145.


Back to previous page
BibTeX entry
	title = {Upper bound approximations for BlockMaxWand},
	author = {Macdonald C. and Tonellotto N.},
	doi = {10.1145/3121050.3121094},
	booktitle = {ICTIR 2017 - 3rd ACM International Conference on the Theory of Information Retrieval, pp. 273–276, Amsterdam, The Netherlands, 1-4 October, 2017},
	year = {2017}