Скачать или смотреть Session 5: Solving Diversity-Aware Maximum Inner Product Search Efficiently and Effectively

RecSys 2022 by Kohei Hirata (Osaka University, Japan), Daichi Amagata (Osaka University, Japan), Sumio Fujita (Yahoo Japan Corporation, Japan), Takahiro Hara (Osaka University, Japan)

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 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 𝑘-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.