Beyond Greedy Search: Pruned Exhaustive Search for Diversified Result Ranking

As a search query can correspond to multiple intents, search result diversification aims at returning a single result list that could satisfy as many users' information needs as possible. However, determining the optimal ranking list is NP-hard. Several algorithms have been proposed to obtain a local optimal ranking with greedy approximations. In this paper, we propose a pruned exhaustive method to generate better solutions than the greedy search. Our approach is based on the observations that there are fewer than ten subtopics for most queries, most relevant results cover only a few subtopics, and most search users only focus on the top results. The proposed pruned exhaustive search algorithm based on ordered pairs (PesOP) finds the optimal solution efficiently. Experimental results based on TREC Diversity and NTCIR Intent task datasets show that PesOP outperforms greedy strategies with better diversification performance. Compared with the original non-pruned exhaustive search, the PesOP algorithm decreases the computational cost while maintaining optimality.