論文の概要: Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2402.04713v1
• Date: Wed, 7 Feb 2024 10:05:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-08 15:49:22.225448
• Title: Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search
• Title（参考訳）: グラフに基づく近似近傍探索のための適応エントリーポイント選択の理論的および実証的解析
• Authors: Yutaro Oguri and Yusuke Matsui
• Abstract要約: グラフベースニアニアニアサーチ(ANNS)における適応エントリーポイント選択の理論的および経験的分析を提案する。 btextit-monotonic path$と$Btextit-MSNETという新しい概念を紹介します。 適応的なエントリポイント選択は、以前の作業よりも一般的な条件下で、固定された中央エントリポイントよりも優れたパフォーマンスの上限を提供することを示す。
• 参考スコア（独自算出の注目度）: 14.832208701208414
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a theoretical and empirical analysis of the adaptive entry point selection for graph-based approximate nearest neighbor search (ANNS). We introduce novel concepts: $b\textit{-monotonic path}$ and $B\textit{-MSNET}$, which better capture an actual graph in practical algorithms than existing concepts like MSNET. We prove that adaptive entry point selection offers better performance upper bound than the fixed central entry point under more general conditions than previous work. Empirically, we validate the method's effectiveness in accuracy, speed, and memory usage across various datasets, especially in challenging scenarios with out-of-distribution data and hard instances. Our comprehensive study provides deeper insights into optimizing entry points for graph-based ANNS for real-world high-dimensional data applications.
• Abstract（参考訳）: 本稿では,グラフに基づく近似近距離探索(anns)における適応的エントリーポイント選択の理論的および経験的解析を行う。 新しい概念を紹介します。 $b\textit{-monotonic path}$と$B\textit{-MSNET}$。 適応的エントリーポイント選択は,従来よりも一般的な条件下において,固定中心エントリーポイントよりも高い性能を示す。 実験では, 分散データとハードインスタンスを用いた課題シナリオにおいて, 様々なデータセットにおける精度, 速度, メモリ使用率において, 手法の有効性を検証する。 本研究は,実世界の高次元データアプリケーションのためのグラフベースの ann のエントリポイント最適化に関する深い知見を提供する。

関連論文リスト

• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  自己組織化マップ(SOM)におけるトポロジカルプロジェクションに基づく半教師付き学習手法を提案する。 提案手法は,まずラベル付きデータ上でSOMを訓練し,最小限のラベル付きデータポイントをキーベストマッチングユニット(BMU)に割り当てる。 提案した最小教師付きモデルが従来の回帰手法を大幅に上回ることを示す。
  論文  参考訳（メタデータ） (2024-01-12T22:51:48Z)
• Chasing Fairness in Graphs: A GNN Architecture Perspective [73.43111851492593]
  グラフニューラルネットワーク(GNN)の統一最適化フレームワーク内で設計されたtextsfFair textsfMessage textsfPassing(FMP)を提案する。 FMPでは、アグリゲーションがまず隣人の情報を活用するために採用され、バイアス軽減ステップにより、人口集団ノードのプレゼンテーションセンタが明示的に統合される。 ノード分類タスクの実験により、提案されたFMPは、実世界の3つのデータセットの公平性と正確性の観点から、いくつかのベースラインを上回っていることが示された。
  論文  参考訳（メタデータ） (2023-12-19T18:00:15Z)
• AMES: A Differentiable Embedding Space Selection Framework for Latent Graph Inference [6.115315198322837]
  Intentional Multi-Embedding Selection (AMES) フレームワークを導入する。 我々のフレームワークは、遅延グラフ推論の従来の手法と比較して、常に同等または優れた結果が得られる。
  論文  参考訳（メタデータ） (2023-11-20T16:24:23Z)
• MinPrompt: Graph-based Minimal Prompt Data Augmentation for Few-shot Question Answering [64.6741991162092]
  オープンドメイン質問応答のための最小限のデータ拡張フレームワークMinPromptを提案する。 我々は、生テキストをグラフ構造に変換し、異なる事実文間の接続を構築する。 次に、グラフアルゴリズムを適用して、原文のほとんどの情報をカバーするのに必要な最小限の文の集合を識別する。 同定された文サブセットに基づいてQAペアを生成し、選択した文に基づいてモデルをトレーニングし、最終モデルを得る。
  論文  参考訳（メタデータ） (2023-10-08T04:44:36Z)
• Optimal Inference in Contextual Stochastic Block Models [0.0]
  属性グラフの教師なしコミュニティ検出のために,文脈ブロックモデル (cSBM) を提案した。 cSBMは、半教師付きノード分類のためのグラフニューラルネットワーク(GNN)の性能を評価するための合成データセットとして広く利用されている。 本稿では,本アルゴリズムが到達した精度と,本論文で提案したGNNアーキテクチャの性能との間には,かなりのギャップが存在することを示す。
  論文  参考訳（メタデータ） (2023-06-06T10:02:57Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport [0.1933681537640272]
  最も近い近傍グラフは、データセットの幾何学や位相を捉えるために広く使われている。 そのようなグラフを構築するための最も一般的な戦略の1つは、各点について最も近い隣人 (kNN) の固定数 k を選択することである。 2次正規化最適輸送に基づく1つのパラメータから適応的近傍グラフを構築するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2022-08-01T04:24:58Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• GPS: A Policy-driven Sampling Approach for Graph Representation Learning [12.760239169374984]
  適応的グラフポリシー駆動サンプリングモデル (GPS) を提案し, 適応的相関計算により各ノードの影響を局所的に評価する。 提案モデルでは,いくつかの重要なベンチマークにおいて既存モデルよりも3%-8%向上し,実世界のデータセットで最先端のパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2021-12-29T09:59:53Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。