論文の概要: Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2505.15636v1
• Date: Wed, 21 May 2025 15:18:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-22 15:42:59.733602
• Title: Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
• Title（参考訳）: グラフベース近傍探索の精度向上のための距離適応ビーム探索
• Authors: Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou, Cameron Musco, Christopher Musco, Torsten Suel,
• Abstract要約: そこで本研究では,ビーム幅に基づくビームサーチのための距離に基づく新しい終端条件を提案する。 探索グラフがナビゲート可能である限り, 得られたアダプティブビームサーチ法は, ほぼ隣り合う問題を解くことが保証されている。 アダプティブビームサーチは、様々なリコール値、データセット、グラフ構造、および最も近い隣人のターゲット数において、標準ビームサーチより優れています。
• 参考スコア（独自算出の注目度）: 23.208935102841103
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have become popular thanks to their empirical accuracy and efficiency. These methods construct a directed graph over the dataset and perform beam search on the graph to find nodes close to a given query. While significant work has focused on practical refinements and theoretical understanding of graph-based methods, many questions remain. We propose a new distance-based termination condition for beam search to replace the commonly used condition based on beam width. We prove that, as long as the search graph is navigable, our resulting Adaptive Beam Search method is guaranteed to approximately solve the nearest-neighbor problem, establishing a connection between navigability and the performance of graph-based search. We also provide extensive experiments on our new termination condition for both navigable graphs and approximately navigable graphs used in practice, such as HNSW and Vamana graphs. We find that Adaptive Beam Search outperforms standard beam search over a range of recall values, data sets, graph constructions, and target number of nearest neighbors. It thus provides a simple and practical way to improve the performance of popular methods.
• Abstract（参考訳）: 最寄りの検索は、機械学習、情報検索、データベースの中心である。 高次元データセットでは、HNSW、DiskANN、NSGといったグラフベースの手法が、その経験的精度と効率によって人気を博している。 これらの手法はデータセット上に有向グラフを構築し、グラフ上でビームサーチを行い、与えられたクエリに近いノードを見つける。 重要な研究は、グラフベースの手法の実践的な洗練と理論的理解に焦点を当ててきたが、多くの疑問が残っている。 そこで本研究では,ビーム幅に基づくビームサーチのための距離に基づく新しい終端条件を提案する。 探索グラフがナビゲート可能である限り、我々の結果であるAdaptive Beam Search法は、ほぼ隣り合う問題を解くことを保証し、ナビゲーション可能性とグラフベースの探索性能の関連性を確立する。 また,HNSWグラフやVamanaグラフなど,実際に使用される約ナビゲート可能なグラフについても,新たな終了条件について広範な実験を行った。 アダプティブビームサーチは、様々なリコール値、データセット、グラフ構造、および最も近い隣人のターゲット数において、標準ビームサーチより優れています。 これにより、一般的なメソッドのパフォーマンスを改善するためのシンプルで実用的な方法を提供する。

関連論文リスト

• Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search [14.832208701208414]
  グラフベースニアニアニアサーチ(ANNS)における適応エントリーポイント選択の理論的および経験的分析を提案する。 btextit-monotonic path$と$Btextit-MSNETという新しい概念を紹介します。 適応的なエントリポイント選択は、以前の作業よりも一般的な条件下で、固定された中央エントリポイントよりも優れたパフォーマンスの上限を提供することを示す。
  論文  参考訳（メタデータ） (2024-02-07T10:05:42Z)
• ProvG-Searcher: A Graph Representation Learning Approach for Efficient Provenance Graph Search [13.627536649679577]
  ProvG-Searcherは,システムセキュリティログ内の既知のAPT動作を検出する新しい手法である。 グラフマッチング問題として前駆体グラフを探索するタスクを定式化し,グラフ表現学習法を用いる。 標準データセットに対する実験結果から,ProvG-Searcherはクエリの振る舞いを検出する精度が99%を超え,優れたパフォーマンスを実現していることが示された。
  論文  参考訳（メタデータ） (2023-09-07T11:29:01Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。 これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。 4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-05-31T10:38:04Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• 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)

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

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