Intractable problems in novelty and diversity

• Simone Santini ^[1] ; Pablo Castells ^[1]
  1. [1] Universidad Autónoma de Madrid

     Universidad Autónoma de Madrid

     Madrid, España

     
• Localización: Actas de las Jornadas de Ingeniería del Software y Bases de Datos (JISBD´11), 2011, ISBN 978-84-9749-486-1, págs. 87-100
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Resumen

  • Information retrieval’s basic problem is retrieving a set of documents relevant for a given query. Here, we present three classes of methods that appeared in the literature, as well as a new one, which is an improvement of the one the three, to retrieve result sets that, in addition to relevance, try to maximize diversity and novelty. We analyze the complexity of these problems and show that whenever relevance, diversity, and novelty are considered together, the methods are all NP-complete.