Local search algorithms for the composite retrieval problem

Abstract

In this paper, we address a problem arising in information retrieval (IR) called composite retrieval problem (CRP) of diverse and complementary bundles. The CRP aims to group items into bundles and then select a subset of such bundles, so that we can maximise the similarity of the items within a bundle and, simultaneously, can maximise the complementarity of the selected bundles. To this end, the CRP approach considers the existing relations among items' attributes, leading to the selection of bundles that satisfy users' expectations without the needing for any refining query and, thus, improving the searching experience, with respect to traditional IR approaches. In this study, we propose three efficient yet straightforward algorithms, namely Local Search, Iterative Local Search and Variable Neighbourhood Search. Further, two different neighbourhood moves are evaluated at each algorithm. Although the first neighbourhood move is focused on the exploitation of the nearby search space, the second one is focused on the exploration of larger portions of the search space. All these algorithms are applied to two real-world publicly available instances and compared to the state-of-the-art algorithms in CRP. Obtained results suggest that combining both neighbourhood moves leads to better results in terms of both, the complementarity of the bundles and similarity of the items. Further, results show that, after statistical analysis, the proposed algorithms are significantly better, for the vast majority of the experiments performed in this study, when compared to the state-of-the-art algorithms in CRP.