カンファレンス (国際) Solving Diversity-Aware Maximum Inner Product Search Efficiently and Effectively

Kohei Hirata (Osaka univ.), Daichi Amagata (Osaka univ.), Takahiro Hara (Osaka univ.), Sumio Fujita

16th ACM Conference on Recommender Systems (RecSys 2022)


Maximum inner product search (or 𝑘-MIPS) is a fundamental operation in recommender systems that infer preferable items for users. To support large-scale recommender systems, existing studies designed scalable 𝑘-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 𝑘-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 𝑘-MIPS problem. This paper overcomes this challenge and proposes IPGreedy, 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 𝑘-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.

Paper : Solving Diversity-Aware Maximum Inner Product Search Efficiently and Effectively (外部サイト)