論文の概要: SHEAF: Self-profiled Hardness Estimation from Answer-set Flux for Predicting Query Hardness in Graph-based ANN Search
- arxiv url: http://arxiv.org/abs/2607.12229v1
- Date: Tue, 14 Jul 2026 00:20:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-15 17:08:29.998706
- Title: SHEAF: Self-profiled Hardness Estimation from Answer-set Flux for Predicting Query Hardness in Graph-based ANN Search
- Title（参考訳）: SHEAF: Answer-set Flux によるグラフベース ANN 検索におけるクエリの硬さ予測のための自己強調ハードネス推定
- Abstract要約: 本稿では,SHEAF (Self-knownd Hardness Estimation from Answer-set Flux) という新しい尺度を提案する。
提案手法は,全問合せにおける各測度を最小限のビームで評価する固定プローブ評価プロトコルを開発した。
- 参考スコア（独自算出の注目度）: 0.9179857807576733
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Graph-based approximate nearest neighbor (ANN) search is usually governed by a beam-width parameter that trades recall for throughput and is fixed for the whole workload. Yet, queries may not be equally hard: for example, on the widely used data set SIFT1M, the beam that a query needs to reach 95\% recall varies by more than $32\times$. Therefore, serving each query at its own width would help if the system could tell, cheaply and in advance, how hard it is. The prevailing proxy for this difficulty is called local intrinsic dimensionality (LID); however, LID is static and geometric, which makes it only weakly predict the minimum beam. This paper presents a new measure, namely Self-profiled Hardness Estimation from Answer-set Flux (SHEAF), which represents a query's hardness as how much its own top-$k$ answer set changes between two shallow probe widths. We design a self-profiling estimator that turns this flux into a deployable per-query beam predictor; furthermore, we develop a fixed-probe evaluation protocol that scores each measure over all queries with an observed minimum sufficient beam. On popular ANN indexes such as CAGRA and HNSW across four diverse data sets, SHEAF predicts the per-query beam better than five baseline measures on both GPU and CPU by up to $1.55\times$ in held-out correlation, using only two shallow probe searches and no query-time ground truth.
- Abstract（参考訳）: グラフベースニアニアニア(ANN)探索は通常、スループットのためにリコールを交換し、ワークロード全体に対して固定されるビーム幅パラメータによって管理される。
例えば、広く使われているデータセットSIFT1Mでは、クエリが95%のリコールに到達する必要があるビームは、32ドル以上の変更がある。
したがって、各クエリを独自の幅で提供することは、システムが判断し、安価に、そして事前に、どれだけ困難であるかを判断するのに役立ちます。
この困難に対する一般的なプロキシは、局所固有次元性(英語版)(LID)と呼ばれるが、LIDは静的で幾何学的であり、最小ビームを弱予測するだけである。
本稿では,SHEAF (Self-knownd Hardness Estimation from Answer-set Flux) という新しい尺度を提案する。
我々は、このフラックスをデプロイ可能なクエリごとのビーム予測器に変換する自己プロファイリング推定器を設計し、さらに、観測された最小限のビームで全てのクエリに対して各測定値を評価する固定プローブ評価プロトコルを開発した。
4つの多様なデータセットにわたるCAGRAやHNSWなどの一般的なANNインデックスでは、SHEAFは、クエリ毎のビームがGPUとCPUのベースラインを最大1.55\times$で予測する。
関連論文リスト
- GridProbe: Posterior-Probing for Adaptive Test-Time Compute in Long-Video VLMs [3.9266376632068485]
GridProbeは、効率的なトレーニング不要な後処理推論パラダイムである。
解答空間における証拠は、凍結したVLM自身の推論を用いて得られる。
疑似関連フレームを適応的に選択し、精度の損失が少なくて、準四分法的な注意コストをもたらす。
論文 参考訳（メタデータ） (2026-05-11T15:57:46Z) - δ-EMG: A Monotonic Graph Index for Approximate Nearest Neighbor Search [33.62724124122037]
本稿では,クエリ時における近似精度を制御する誤り境界付きANN探索アルゴリズムを提案する。
0.99のリコール条件下では、SIFT1Mデータセット上で19,000QPSを達成し、他の手法よりも40%以上性能が向上する。
論文 参考訳（メタデータ） (2025-11-21T03:20:54Z) - $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
$textttSPECS$は、投機的デコードにインスパイアされた遅延対応のテスト時間スケーリングメソッドである。
我々の結果は、$textttSPECS$matchはビームサーチの精度を上回り、最大$sim$19.1%のレイテンシを削減していることを示している。
論文 参考訳（メタデータ） (2025-06-15T05:50:05Z) - Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search [23.208935102841103]
そこで本研究では,ビーム幅に基づくビームサーチのための距離に基づく新しい終端条件を提案する。
探索グラフがナビゲート可能である限り, 得られたアダプティブビームサーチ法は, ほぼ隣り合う問題を解くことが保証されている。
アダプティブビームサーチは、様々なリコール値、データセット、グラフ構造、および最も近い隣人のターゲット数において、標準ビームサーチより優れています。
論文 参考訳（メタデータ） (2025-05-21T15:18:53Z) - A Bi-metric Framework for Fast Similarity Search [23.254885582600775]
近接するデータ構造を設計するための新しい「バイメトリック」フレームワークを提案する。
本フレームワークでは, 高精度で計算に費用がかかる基底トラストメトリックと, 安価だが精度の低いプロキシメトリックの2つの相似性関数を仮定する。
プロキシメトリックのみを使用して、両方のメトリクスに対して限られた数の呼び出ししか使用せず、データ構造を構築する方法を示す。
論文 参考訳（メタデータ） (2024-06-05T03:17:48Z) - Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
効率的かつ適応的な予測を実現するために,ワンショットサブグラフリンク予測を提案する。
設計原理は、KG全体に直接作用する代わりに、予測手順を2つのステップに分離する。
5つの大規模ベンチマークにおいて,効率の向上と性能の向上を実現している。
論文 参考訳（メタデータ） (2024-03-15T12:00:12Z) - Camera Based mmWave Beam Prediction: Towards Multi-Candidate Real-World
Scenarios [15.287380309115399]
本稿では,実環境におけるV2Iシナリオにおけるセンシング支援ビーム予測問題について広範囲に検討する。
特に,視覚的および位置的データを用いて最適なビーム指標を予測することを提案する。
提案手法は,大規模実世界のDeepSense 6$Gデータセットを用いて評価する。
論文 参考訳（メタデータ） (2023-08-14T00:15:01Z) - Fast Beam Alignment via Pure Exploration in Multi-armed Bandits [91.11360914335384]
我々は,ミリ波通信におけるBAレイテンシを低減するために,帯域幅に基づく高速BAアルゴリズムを開発した。
我々のアルゴリズムは2相ヘテロセダスティックトラック・アンド・ストップ (2PHT&S) と呼ばれる。
論文 参考訳（メタデータ） (2022-10-23T05:57:39Z) - IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。
クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。
我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文 参考訳（メタデータ） (2021-03-17T23:13:25Z) - Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。
本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。
実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
論文 参考訳（メタデータ） (2020-07-20T12:07:48Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。