Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.13445 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908325754437632 |
|---|---|
| author | Amagata, Daichi Aoayama, Kazuyoshi Kido, Keito Fujita, Sumio |
| author_facet | Amagata, Daichi Aoayama, Kazuyoshi Kido, Keito Fujita, Sumio |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_13445 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How to Mine Potentially Popular Items? A Reverse MIPS-based Approach Amagata, Daichi Aoayama, Kazuyoshi Kido, Keito Fujita, Sumio Databases 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. |
| title | How to Mine Potentially Popular Items? A Reverse MIPS-based Approach |
| topic | Databases |
| url | https://arxiv.org/abs/2504.13445 |