An Approach to Capturing Balance between Retrieval Effectiveness and Efficiency

Abstract:

It has been shown that learning to rank approaches are capable of learning highly effective ranking functions. However, these approaches have mostly ignored the important issue of efficiency. Given that both efficiency and effectiveness are important for real search engines, models that are optimized for effectiveness may not meet the strict efficiency requirements necessary to deploy in a production environment. In this work, we present a unified framework for jointly optimizing effectiveness and efficiency. We propose new metrics that capture the tradeoff between these two competing forces and devise a strategy for automatically learning models that directly optimize the tradeoff metrics. Experiments indicate that models learned in this way provide a good balance between retrieval effectiveness and efficiency. With specific loss functions, learned models converge to familiar existing ones, which demonstrate the generality of our framework. Finally, we show that our approach naturally leads to a reduction in the variance of query execution times, which is important for query load balancing and user satisfaction.

• Periodical: Advanced Materials Research (Volumes 268-270)
• Pages: 1773-1779
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.268-270.1773
• Online since: July 2011
• Authors: Ke Xu, Long Fei Li
• Keywords: Effectiveness Tradeoff, Efficiency Tradeoff, Efficient Sequentail Dependence, Learning to Rank, Linear Model

References

[1] V. Anh and A. Moffat. Pruned query evaluation using pre-computed impacts. SIGIR, p.372–379, (2006).

DOI: 10.1145/1148170.1148235

[2] J. Bai, Y. Chang, H. Cui, Z. Zheng, G. Sun, and X. Li. Investigation of partial query proximity in web search. WWW, p.1183–1184, (2008).

DOI: 10.1145/1367497.1367717

[3] M. Bendersky, W. Croft, and D. Smith. Two-stage query segmentation for information retrieval. SIGIR, p.810–811, (2009).

DOI: 10.1145/1571941.1572140

[4] M. Bendersky, D. Metzler, and W. Croft. Learning concept importance using a weighted dependence model. WSDM, p.31–40, (2010).

[5] C. Burges, T. Shaked, E. Renshaw, A. Lazier, M. Deeds, N. Hamilton, and G. Hullender. Learning to rank using gradient descent. ICML, p.89–96, (2005).

DOI: 10.1145/1102351.1102363

[6] S. Buttcher and C. Clarke. Efficiency vs. effectiveness in terabyte-scale information retrieval. TREC, (2005).

[7] S. Buttcher, C. Clarke, and P. Yeung. Indexing pruning and result reranking: Effects on ad-hoc retrieval and named page finding. TREC, (2006).

[8] M. Lease. An improved Markov Random Field model for supporting verbose queries. SIGIR, p.476–483, (2009).

DOI: 10.1145/1571941.1572023

[9] T. -Y. Liu. Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 3(3): 225–331, (2009).

DOI: 10.1561/1500000016

[10] D. Metzler and W. Croft. A Markov Random Field model for term dependencies. SIGIR, p.472–479, (2005).

[11] D. Metzler and W. Croft. Linear feature-based models for information retrieval. Information Retrieval, 10(3): 257–274, (2007).

DOI: 10.1007/s10791-006-9019-z

[12] A. Ntoulas and J. Cho. Pruning policies for two-tiered inverted index with correctness guarantee. SIGIR, p.191–198, (2007).

DOI: 10.1145/1277741.1277776

[13] J. Ponte and W. Croft. A language modeling approach to information retrieval. SIGIR, p.275–281, (1998).

[14] S. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford. Okapi at TREC-3. TREC, p.109–126, (1994).

[15] T. Strohman, H. Turtle, and W. Croft. Optimization strategies for complex queries. SIGIR, p.219–225, (2005).

[16] T. Tao and C. Zhai. An exploration of proximity measures in information retrieval. SIGIR, p.295–302, (2007).

[17] Xu Ke, Chen Youjun. Recognition of Remote Sensing Target Based on Wavelet Transform and Support Vector Machine. Journal of South-Central University of Nationalities. 27(2009), pp.95-98.

[18] L. Wang, J. Lin and D. Metzler. Learning to efficiently rank. SIGIR, pp.138-145, (2010).