Balancing Relevance and Diversity in k-Maximum Inner Product Search

In this paper, we investigate Diversity-aware k-Maximum Inner Product Search (DkMIPS), an essential problem in recommendation and information retrieval tasks where balancing relevance and diversity is crucial for user satisfaction and engagement. Vanilla kMIPS prioritizes relevance over diversity, often yielding highly homogeneous search results. In addition, existing DkMIPS methods remain limited in effectiveness and efficiency. To address these issues, we introduce a novel DkMIPS formulation that integrates relevance and diversity into a unified objective, with a controllable parameter λ that allows users to adjust the level of diversity to their specific needs. We propose two scan-based algorithms, Greedy and DualGreedy, that leverage submodularity to provide DkMIPS results with theoretical guarantees. Furthermore, we incorporate a lightweight Ball-Cone Tree (BC-Tree) index to improve the query efficiency of Greedy and DualGreedy. Extensive experiments on real-world datasets for recommendation and document retrieval tasks show that our proposed algorithms consistently achieve a better balance between diversity and relevance than several state-of-the-art kMIPS and DkMIPS methods, while outperforming existing DkMIPS methods in terms of efficiency and scalability. Our code is publicly available at https://github.com/HuangQiang/DiverseMIPS.