Document - Upper bound approximations for BlockMaxWand

2017

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

Citations

[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.

Metrics

Back to previous page

Cite as

BibTeX entry

@inproceedings{oai:it.cnr:prodotti:384714,
	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}
}