Publications
OTHERS (INTERNATIONAL) How to Mine Potentially Popular Items? A Reverse MIPS-based Approach
Daichi Amagata (Osaka University), Kazuyoshi Aoyama (Osaka University), Keito Kido (Osaka University), Sumio Fujita
arXiv.org (arXiv)
April 18, 2025
The 𝑘-MIPS (𝑘 Maximum Inner Product Search) problem has been employed in many fields. Recently, its reverse version, the reverse 𝑘-MIPS problem, has been proposed. Given an item vector (i.e., query), it retrieves all user vectors such that their 𝑘-MIPS results contain the item vector. Consider the cardinality of a reverse 𝑘- MIPS result. A large cardinality means that the item is potentially popular, because it is included in the 𝑘-MIPS results of many users. This mining is important in recommender systems, market analysis, and new item development. Motivated by this, we formulate a new problem. In this problem, the score of each item is defined as the cardinality of its reverse 𝑘-MIPS result, and the 𝑁 items with the highest score are retrieved. A straightforward approach is to compute the scores of all items, but this is clearly prohibitive for large numbers of users and items.We remove this inefficiency issue and propose a fast algorithm for this problem. Because the main bottleneck of the problem is to compute the score of each item, we devise a new upper-bounding technique that is specific to our problem and filters unnecessary score computations. We conduct extensive experiments on real datasets and show the superiority of our algorithm over competitors.
Paper :
How to Mine Potentially Popular Items? A Reverse MIPS-based Approach
(external link)