Approximation algorithms for diversified search ranking

N. Bansal, K. Jain, A. Kazeykina, J. Naor

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    13 Citaten (Scopus)


    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.
    Originele taal-2Engels
    TitelAutomata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part II)
    RedacteurenS. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, P.G. Spirakis
    Plaats van productieBerlin
    ISBN van geprinte versie978-3-642-14161-4
    StatusGepubliceerd - 2010

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'Approximation algorithms for diversified search ranking'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit