論文の概要: SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner
Product Search
- arxiv url: http://arxiv.org/abs/2211.12751v1
- Date: Wed, 23 Nov 2022 07:26:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-24 16:35:08.243149
- Title: SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner
Product Search
- Title（参考訳）: SAH: 逆$k$-maximum内積探索のためのシフト対応非対称ハッシュ
- Authors: Qiang Huang, Yanhao Wang, Anthony K. H. Tung
- Abstract要約: 本稿では,Reverse $k$-maximum inner Product Search (R$k$MIPS) と呼ばれる新たな課題について検討する。
クエリ(item)ベクトル、アイテムベクトルのセット、およびユーザベクトルのセットが与えられた場合、R$k$MIPSの問題は、クエリベクトルの内積がクエリとアイテムベクトルの中で最大であるユーザベクトルのセットを見つけることである。
我々は、R$k$MIPSに取り組むために、シフト対応非対称ハッシュ(SAH:Shifting-aware Asymmetric Hashing)と呼ばれる、最初の準四進時間アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 17.50372620319673
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper investigates a new yet challenging problem called Reverse
$k$-Maximum Inner Product Search (R$k$MIPS). Given a query (item) vector, a set
of item vectors, and a set of user vectors, the problem of R$k$MIPS aims to
find a set of user vectors whose inner products with the query vector are one
of the $k$ largest among the query and item vectors. We propose the first
subquadratic-time algorithm, i.e., Shifting-aware Asymmetric Hashing (SAH), to
tackle the R$k$MIPS problem. To speed up the Maximum Inner Product Search
(MIPS) on item vectors, we design a shifting-invariant asymmetric
transformation and develop a novel sublinear-time Shifting-Aware Asymmetric
Locality Sensitive Hashing (SA-ALSH) scheme. Furthermore, we devise a new
blocking strategy based on the Cone-Tree to effectively prune user vectors (in
a batch). We prove that SAH achieves a theoretical guarantee for solving the
RMIPS problem. Experimental results on five real-world datasets show that SAH
runs 4$\sim$8$\times$ faster than the state-of-the-art methods for R$k$MIPS
while achieving F1-scores of over 90\%. The code is available at
\url{https://github.com/HuangQiang/SAH}.
- Abstract（参考訳）: 本稿では,Reverse $k$-Maximum inner Product Search (R$k$MIPS) と呼ばれる新たな課題について検討する。
クエリ(item)ベクター、アイテムベクターの集合、およびユーザベクターの集合が与えられたとき、r$k$mipsの問題は、クエリベクターを持つ内積がクエリベクターとアイテムベクターのうち最大の$k$の1つであるユーザベクターの集合を見つけることである。
我々は、R$k$MIPS問題に対処するために、第1の準四進時間アルゴリズム、すなわちシフト対応非対称ハッシュ(SAH)を提案する。
項目ベクトル上での最大内積探索(MIPS)を高速化するために、シフト不変な非対称変換を設計し、新しいサブ線形時間シフト型非対称局所性感性ハッシュ(SA-ALSH)方式を開発する。
さらに,conan-treeに基づく新たなブロッキング戦略を考案し,(バッチ内で)ユーザベクトルを効果的にプルーピングする。
RMIPS問題を解くための理論的保証をSAHが達成していることを示す。
5つの実世界のデータセットの実験結果から、SAHはR$k$MIPSの最先端メソッドよりも高速に4$\sim$8$\times$を実行し、F1スコアの90%以上を達成した。
コードは \url{https://github.com/huangqiang/sah} で入手できる。
関連論文リスト
- SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。
我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
論文 参考訳（メタデータ） (2024-12-30T18:59:46Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings [15.275864151890511]
マルチベクトル探索を単一ベクトル類似性探索に還元する検索機構であるMUVERA(MUlti-VEctor Retrieval Algorithm)を導入する。
MUVERAはBEIR検索データセットの多種多様なセットに対して、一貫して優れたエンドツーエンドのリコールとレイテンシを実現する。
論文 参考訳（メタデータ） (2024-05-29T20:40:20Z) - Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。
Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
論文 参考訳（メタデータ） (2024-02-11T16:36:48Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Faster Maximum Inner Product Search in High Dimensions [17.040520467777295]
最大内部製品探索(MIPS)は、リコメンデーションシステムなどの機械学習アプリケーションにおいて、ユビキタスなタスクである。
複雑度が$d$に依存しない新しいランダム化MIPSアルゴリズムであるBanditMIPSを提案する。
我々は、BanditMIPSが正しい答えを高い確率で返し、$d$を$O(sqrtd)$から$O(1)$に改善する理論的な保証を提供する。
論文 参考訳（メタデータ） (2022-12-14T23:46:23Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。