Solving Diversity-Aware Maximum Inner Product Search Efficiently and Effectively
Kohei Hirata, Daichi Amagata, Sumio Fujita, Takahiro Hara · 2022
Maximum inner product search (or k-MIPS) is a fundamental operation in recommender systems that infer preferable items for users. To support large-scale recommender systems, existing studies designed scalable k-MIPS algorithms. However, these studies do not consider diversity, although recommending diverse items is important to improve user satisfaction. We therefore formulate a new problem, namely diversity-aware k-MIPS. In this problem, users can control the degree of diversity in their recommendation lists through a parameter. However, exactly solving this problem is unfortunately NP-hard, so it is challenging to devise an efficient, effective, and practical algorithm for the diversity-aware k-MIPS problem. This paper overcomes this challenge and proposes IP-Greedy, which incorporates new early termination and skipping techniques into a greedy algorithm. We conduct extensive experiments on real datasets, and the results demonstrate the efficiency and effectiveness of our algorithm. Also, we conduct a case study of the diversity-aware k-MIPS problem on a real dataset. We confirm that this problem can make recommendation lists diverse while preserving high inner products of user and item vectors in the lists.