論文の概要: General and Practical Tuning Method for Off-the-Shelf Graph-Based Index:
SISAP Indexing Challenge Report by Team UTokyo
- arxiv url: http://arxiv.org/abs/2309.00472v1
- Date: Fri, 1 Sep 2023 14:11:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-04 13:21:39.929807
- Title: General and Practical Tuning Method for Off-the-Shelf Graph-Based Index:
SISAP Indexing Challenge Report by Team UTokyo
- Title(参考訳): オフザシェルフグラフベースインデックスの汎用的および実践的チューニング手法:UTOkyoチームによるSISAPインデクシングチャレンジレポート
- Authors: Yutaro Oguri and Yusuke Matsui
- Abstract要約: 本研究では,市販のグラフベースインデックスの性能をチューニングする手法を提案する。
我々はブラックボックス最適化アルゴリズムを用いて、必要なリコールレベルと待ち時間(QPS)を満たす統合チューニングを行う。
SISAP 2023 Indexing Challengeの10万トラックと3000万トラックで2位になった。
- 参考スコア(独自算出の注目度): 14.832208701208414
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite the efficacy of graph-based algorithms for Approximate Nearest
Neighbor (ANN) searches, the optimal tuning of such systems remains unclear.
This study introduces a method to tune the performance of off-the-shelf
graph-based indexes, focusing on the dimension of vectors, database size, and
entry points of graph traversal. We utilize a black-box optimization algorithm
to perform integrated tuning to meet the required levels of recall and Queries
Per Second (QPS). We applied our approach to Task A of the SISAP 2023 Indexing
Challenge and got second place in the 10M and 30M tracks. It improves
performance substantially compared to brute force methods. This research offers
a universally applicable tuning method for graph-based indexes, extending
beyond the specific conditions of the competition to broader uses.
- Abstract(参考訳): ANN (Approximate Nearest Neighbor) 探索のためのグラフベースのアルゴリズムの有効性にもかかわらず、そのようなシステムの最適チューニングは未だ不明である。
本研究は,グラフトラバーサルのベクトル,データベースサイズ,エントリポイントの次元に着目し,既定のグラフベースインデックスの性能をチューニングする手法を提案する。
ブラックボックス最適化アルゴリズムを用いて,要求されるリコールとクエリ毎秒(qps)のレベルを満たすための統合チューニングを行う。
我々はsisap 2023インデクシングチャレンジのタスクaに本手法を適用し,10mおよび30mトラックで2位となった。
ブリュート力法に比べて性能が大幅に向上する。
この研究は、グラフベースのインデックスに対して普遍的に適用可能なチューニング方法を提供し、より広い用途への競争の具体的条件を超えて拡張する。
関連論文リスト
- SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search [13.349178274732862]
我々は、量子化とグラフのよりシンフォニーな統合を実現するSymphonyQGを提案する。
実世界のデータセットに関する広範な実験に基づいて、SymphonyQGは、時間精度のトレードオフの観点から、新たな最先端技術を確立している。
論文 参考訳(メタデータ) (2024-11-19T04:51:08Z) - Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search [3.934351369702082]
高次元空間における近似近接探索(ANNS)は、機械学習分野における重要な課題である。
本稿では,グラフ内のノードの近傍を探索する際の確率的保証を提供する手法を提案する。
次に,グラフ内のどの近傍が正確な距離計算を行うべきかを効率的に同定する新しい手法PEOを紹介する。
論文 参考訳(メタデータ) (2024-02-17T18:08:37Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳(メタデータ) (2023-10-05T02:58:29Z) - 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) - Learning Heuristics for the Maximum Clique Enumeration Problem Using Low
Dimensional Representations [0.0]
本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。
本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。
分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
論文 参考訳(メタデータ) (2022-10-30T22:04:32Z) - FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor
Search [20.928821121591493]
効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。
FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。
実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
論文 参考訳(メタデータ) (2022-06-22T22:30:46Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳(メタデータ) (2022-05-06T03:37:00Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-03-28T21:34:16Z) - 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) - ZARTS: On Zero-order Optimization for Neural Architecture Search [94.41017048659664]
微分可能なアーキテクチャサーチ (DARTS) は、NASの高効率性のため、一般的なワンショットパラダイムである。
この作業はゼロオーダーの最適化に変わり、上記の近似を強制せずに探索するための新しいNASスキームであるZARTSを提案する。
特に、12ベンチマークの結果は、DARTSの性能が低下するZARTSの顕著な堅牢性を検証する。
論文 参考訳(メタデータ) (2021-10-10T09:35:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。