Publications
カンファレンス (国内) 逆k-MIPSに基づく影響力の大きいアイテムの高速検索
青山 和禎 (阪大), 天方 大地 (阪大), 藤田 澄男, 原 隆浩 (阪大)
第16回データ工学と情報マネジメントに関するフォーラム（第22回日本データベース学会年次大会） (DEIM 2024)
2024.4.1
近年，最大内積探索（k-MIPS）が多くのアプリケーションに応用されている．特に推薦システムにおい て，ユーザがアイテムに対して行う評価を予測し，評価予測値の高い上位k 個のアイテムを検索するk-MIPS 問題 を解くことが一般的である．また，あるアイテムをk-MIPS 結果に含むユーザの集合を検索する逆k-MIPS（reverse k-MIPS）問題がある．多くのユーザのk-MIPS 結果に入るアイテムは影響力が強いといえるため，あるアイテムの 影響力は，そのアイテムの逆k-MIPS の結果のカーディナリティと定義できる．本論文では，逆k-MIPS に基づく影 響力の大きいアイテムの検索問題を扱う．この問題は，アイテム集合，ユーザ集合，k，およびN が与えられたとき， スコアの大きいN 個のアイテムを探索する問題であり，あるアイテムのスコアはそのアイテムをk-MIPS 結果に含む ユーザの数である．我々は，この問題を高速に解くためのアルゴリズムを提案する．提案アルゴリズムは，前処理に おいて，O(nm) 時間で各アイテムのスコアの上界値を計算する（n およびm それぞれユーザ数およびアイテム数）． オンラインでは，前処理で計算した上界値を使って不要な逆k-MIPS の計算を枝刈りする．実世界のデータを用いた 実験により，提案アルゴリズムが既存の技術と比較して優れた性能であることを示す．
Paper :
逆k-MIPSに基づく影響力の大きいアイテムの高速検索
（外部サイト）