Abstract
A fundamental issue in Web search is ranking search results based on user logs, since different users may have different preferences and intents with regards to a search query. Also, in many search query applications, users tend to look at only the top part of the ranked result list in order to find relevant documents. The setting we consider contains various types of users, each of which is interested in a subset of the search results. The goal is to rank the search results of a query providing highly ranked relevant results. Our performance measure is the discounted cumulative gain which offers a graded relevance scale of documents in a search engine result set, and measures the usefulness (gain) of a document based on its position in the result list. Based on this measure, we suggest a general approach to developing approximation algorithms for ranking search results that captures different aspects of users’ intents. We also take into account that the relevance of one document cannot be treated independently of the relevance of other documents in a collection returned by a search engine. We first consider the scenario where users are interested in only a single search result (e.g., navigational queries). We then develop a polynomial time approximation scheme for this case. We further consider the general case where users have different requirements on the number of search results, and develop efficient approximation algorithms. Finally, we consider the problem of choosing the top k out of n search results and show that for this problem (1 − 1/e) is indeed the best approximation factor achievable, thus separating the approximability of the two versions of the problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Gollapudi, S., Halverson, A., Ieong, S.: Diversifying search results. In: WSDM 2009, pp. 5–14 (2009)
Azar, Y., Gamzu, I., Yin, X.: Multiple intents re-ranking. In: STOC 2009: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 669–678. ACM, New York (2009)
Bansal, N., Gupta, A., Krishnaswamy, R.: A constant factor approximation algorithm for generalized min-sum set cover. In: Symposium on Discrete Algorithms, SODA (2010)
Carbonell, J., Goldstein, J.: The use of MMR, diversity-based reranking for reordering documents and producing summaries. In: SIGIR 1998, pp. 335–336 (1998)
Carr, R., Fleischer, L., Leung, V., Phillips, C.: Strengthening integrality gaps for capacitated network design and covering problems. In: Symposium on Discrete Algorithms (SODA), pp. 106–115 (2000)
Chen, H., Karger, D.R.: Less is more: probabilistic models for retrieving fewer relevant documents. In: SIGIR 2006, pp. 429–436 (2006)
Clarke, C.L.A., Kolla, M., Cormack, G.V., Vechtomova, O., Ashkan, A., Bttcher, S., MacKinnon, I.: Novelty and diversity in information retrieval evaluation. In: SIGIR ’08, pp. 659–666 (2008)
Croft, B., Metzler, D., Strohman, T.: Search Engines: Information Retrieval in Practice. Addison-Wesley, Reading (2009)
Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29(3), 410–421 (2001)
Manning, C.D., Raghavan, P., Schuetze, H.: Introduction to Information Retrieval. Cambridge University Press, New York (2008)
Radlinski, F., Dumais, S.T.: Improving personalized web search using result diversification. In: SIGIR 2006, pp. 691–692 (2006)
Radlinski, F., Kleinberg, R., Joachims, T.: Learning diverse rankings with multi-armed bandits. In: ICML 2008, pp. 784–791 (2008)
Vee, E., Srivastava, U., Shanmugasundaram, J., Bhat, P., Yahia, S.A.: Efficient computation of diverse query results. In: ICDE 2008, pp. 228–236 (2008)
Zhai, C., Cohen, W.W., Lafferty, J.D.: Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In: SIGIR 2003, pp. 10–17 (2003)
Ziegler, C.-N., McNee, S.M., Konstan, J.A., Lausen, G.: Improving recommendation lists through topic diversification. In: WWW 2005, pp. 22–32 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bansal, N., Jain, K., Kazeykina, A., Naor, J.(. (2010). Approximation Algorithms for Diversified Search Ranking. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds) Automata, Languages and Programming. ICALP 2010. Lecture Notes in Computer Science, vol 6199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14162-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-14162-1_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14161-4
Online ISBN: 978-3-642-14162-1
eBook Packages: Computer ScienceComputer Science (R0)