論文の概要: Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems
- arxiv url: http://arxiv.org/abs/2609.16850v1
- Date: Tue, 15 Sep 2026 08:42:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 14:56:08.418945
- Title: Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems
- Title（参考訳）: 大規模リコメンダシステムにおける検索のための効率的なスウィング計算
- Abstract要約: 我々は、ASCと$K$ASCという2つの新しいアルゴリズムと、K$Swingクエリの上位2つを提示する。
これらのアルゴリズムは、Swing値の確率的相対的および加法的誤差において厳密な理論的保証を提供する。
- 参考スコア（独自算出の注目度）: 12.932134727922245
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a user-item graph $G$, a query item $v_q$ and a target item $v_t$, the Swing score $sw(v_q, v_t)$ of the item pair $(v_q, v_t)$ leverages the user-item-user interaction structure to evaluate their similarity. This measure is found to be highly effective in item-to-item (i2i) retrieval task and finds extensive applications in industrial-scale recommender systems. However, existing solutions towards computing Swing scores are either prohibitively expensive due to their quadratic time complexity w.r.t. the item degree, or rely on truncation heuristics that yield unsatisfactory quality, rendering them impractical particularly on graphs with billions of interactions. In this paper, we present ASC and $K$-ASC, two novel and efficient algorithms for approximate and top-$K$ Swing queries, to address the aforementioned limitations. Specifically, these algorithms provide rigorous theoretical guarantees in probabilistic relative and additive errors of Swing values. The basic idea of ASC is to combine two randomized algorithms, GNS and USS, in a simple yet non-trivial way to adaptively process high- and low-degree query items with minimal runtime cost. In particular, $K$-ASC offers practical efficiency and effectiveness for top-$K$ queries through a filter-refinement paradigm with carefully-designed heuristics. Extensive experiments over eight real datasets demonstrate that ASC and $K$-ASC can achieve orders of magnitude speed-up over competitors in terms of computational time while offering the same approximate and top-$K$ query result quality, and in particular, $K$-ASC is highly efficient on massive graphs including the billion-edge Yambda and MAG datasets.
- Abstract（参考訳）: ユーザ-itemグラフ$G$、クエリアイテム$v_q$、ターゲットアイテム$v_t$、アイテムペア$(v_q, v_t)$のSwingスコア$sw(v_q, v_t)$は、ユーザ-item-ユーザインタラクション構造を利用して、その類似性を評価する。
この尺度は,i2i検索作業において極めて有効であることが確認され,産業規模のレコメンデータシステムに広く応用されている。
しかしながら、Swingのスコアを計算するための既存のソリューションは、アイテムの次数的時間的複雑性(英語版)が原因で禁止的に高価であるか、あるいは不満足な品質をもたらすトラニケーション・ヒューリスティック(英語版)に依存しているため、特に数十億の相互作用を持つグラフでは非現実的である。
本稿では、上記の制限に対処するため、ASC と $K$-ASC という2つの新しいアルゴリズムを提案する。
具体的には、これらのアルゴリズムはSwing値の確率的相対的および加法的誤差において厳密な理論的保証を提供する。
ASCの基本的な考え方は、高次および低次クエリアイテムを最小のランタイムコストで適応的に処理する単純な方法で、GNSとUSSという2つのランダム化アルゴリズムを組み合わせることである。
特に、$K$-ASCは、慎重に設計されたヒューリスティックなフィルタ精製パラダイムを通じて、上位$K$クエリの実用的効率と有効性を提供する。
8つの実データセットに対する大規模な実験により、ASCと$K$-ASCは、計算時間に関して競合よりも桁違いのスピードアップを達成でき、同じ近似と上位の$K$クエリ結果の品質を提供し、特に10億エッジのYambdaやMAGデータセットを含む巨大なグラフ上では、$K$-ASCは非常に効率的である。
関連論文リスト
- $\ exttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
$textttSPECS$は、投機的デコードにインスパイアされた遅延対応のテスト時間スケーリングメソッドである。
我々の結果は、$textttSPECS$matchはビームサーチの精度を上回り、最大$sim$19.1%のレイテンシを削減していることを示している。
論文 参考訳（メタデータ） (2025-06-15T05:50:05Z) - Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice [0.0]
我々は、上位k$選択のための公平な線形スコアリング関数を同定する問題に対処する。
既存のアルゴリズムは特に高次元において効率的にスケールしない。
我々は、この効率のポテンシャルを、実用的なパフォーマンス向上を実現する最適化されたアルゴリズムに変える。
論文 参考訳（メタデータ） (2025-03-14T16:40:36Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Efficient and Accurate Top-$K$ Recovery from Choice Data [1.14219428942199]
レコメンデーションシステムのようないくつかのアプリケーションでは、統計学者は主に大量のアイテムから上位のアイテムの集合を回収することに興味がある。
そこで本稿では,K$-recoveryの高速かつ高精度なランキングアルゴリズムとして,選択に基づくボルダカウントアルゴリズムを提案する。
選択に基づくボルダカウントアルゴリズムは,多種多様なランダム効用モデルの下で,上位$Kの回収に最適なサンプル複雑性を有することを示す。
論文 参考訳（メタデータ） (2022-06-23T22:05:08Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - How to Query An Oracle? Efficient Strategies to Label Data [59.89900843097016]
機械学習におけるデータセットのラベル付けに専門家の託宣を照会する際の基本的な問題について考察する。
本稿では,サンプルをラベル付けするために,ラウンド・バイ・ラウンドでランダム化されたバッチアルゴリズムを提案し,クエリレートが$O(fracNk2)$であることを示す。
さらに,適応型グリージークエリ方式を提案し,三重項クエリを用いたサンプルあたり平均$approx 0.2N$クエリを実現する。
論文 参考訳（メタデータ） (2021-10-05T20:15:35Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and
Designing Experiments [30.592069659778716]
MECのサイズは、介入を行うことで真の因果グラフを回復するための複雑さの尺度である。
そこで本稿では, 介入結果の可能なMECに対して, 効率的な反復法を提案する。
提案手法は,MECの規模を計算し,実験による設計が最先端の手法であることを示す。
論文 参考訳（メタデータ） (2020-06-17T05:51:34Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。