2025/04/18 by Amagata, Daichi, Aoayama, Kazuyoshi, Kido, Keito +1
#Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2504.13445
The k-MIPS (k Maximum Inner Product Search) problem has been employed in many fields. Recently, its reverse version, the reverse k-MIPS problem, has been proposed. Given an item vector (i.e., query), it retrieves all user vectors such that their k-MIPS results contain the item vector. Consider the cardinality of a reverse k-MIPS result. A large cardinality means that the item is potentially popular, because it is included in the k-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 k-MIPS result, and the N 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.