Minimally Complete Retrieval in Recommender Systems

Most retrieval algorithms in recommender systems are incomplete in the sense that the existence of a product that satisfies a given subset of the constraints in a user’s query does not guarantee that such a product will be retrieved. Moreover, no existing retrieval algorithm is minimally complete (i.e., always produces a retrieval set of the smallest possible size required for completeness). In this paper, we present an algorithm for minimally complete retrieval called MCR-1 and show how similarity can also be used to inform the retrieval process. We also present theoretical results that enable the maximum possible size of the MCR-1 retrieval set to be determined for a given query, and show empirically that the algorithm tends to produce much smaller retrieval sets than are possible in theory as query size increases.