論文の概要: SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search
- arxiv url: http://arxiv.org/abs/2411.12229v1
- Date: Tue, 19 Nov 2024 04:51:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-20 13:34:59.592803
- Title: SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search
- Title（参考訳）: SymphonyQG: 近似近傍探索のための量子化とグラフのシンフォニー統合を目指して
- Authors: Yutong Gou, Jianyang Gao, Yuexuan Xu, Cheng Long,
- Abstract要約: 我々は、量子化とグラフのよりシンフォニーな統合を実現するSymphonyQGを提案する。
実世界のデータセットに関する広範な実験に基づいて、SymphonyQGは、時間精度のトレードオフの観点から、新たな最先端技術を確立している。
- 参考スコア（独自算出の注目度）: 13.349178274732862
- License:
- Abstract: Approximate nearest neighbor (ANN) search in high-dimensional Euclidean space has a broad range of applications. Among existing ANN algorithms, graph-based methods have shown superior performance in terms of the time-accuracy trade-off. However, they face performance bottlenecks due to the random memory accesses caused by the searching process on the graph indices and the costs of computing exact distances to guide the searching process. To relieve the bottlenecks, a recent method named NGT-QG makes an attempt by integrating quantization and graph. It (1) replicates and stores the quantization codes of a vertex's neighbors compactly so that they can be accessed sequentially, and (2) uses a SIMD-based implementation named FastScan to efficiently estimate distances based on the quantization codes in batch for guiding the searching process. While NGT-QG achieves promising improvements over the vanilla graph-based methods, it has not fully unleashed the potential of integrating quantization and graph. For instance, it entails a re-ranking step to compute exact distances at the end, which introduces extra random memory accesses; its graph structure is not jointly designed considering the in-batch nature of FastScan, which causes wastes of computation in searching. In this work, following NGT-QG, we present a new method named SymphonyQG, which achieves more symphonious integration of quantization and graph (e.g., it avoids the explicit re-ranking step and refines the graph structure to be more aligned with FastScan). Based on extensive experiments on real-world datasets, SymphonyQG establishes the new state-of-the-art in terms of the time-accuracy trade-off.
- Abstract（参考訳）: 高次元ユークリッド空間における近似近傍探索(ANN)は幅広い応用がある。
既存のANNアルゴリズムの中で、グラフベースの手法は時間精度のトレードオフという点で優れた性能を示している。
しかし、グラフインデックス上の探索プロセスによるランダムメモリアクセスと、探索プロセスを導くための正確な距離の計算コストにより、パフォーマンス上のボトルネックに直面している。
ボトルネックを緩和するため、NGT-QGと呼ばれる最近の手法では量子化とグラフを統合する試みが行われている。
1) 頂点の隣人の量子化符号をコンパクトに複製保存し、連続的にアクセスできるようにし、(2) SIMD ベースのFastScan という実装を用いて、探索プロセスを導くためにバッチ内の量子化符号に基づいて距離を効率的に推定する。
NGT-QGは、バニラグラフベースの手法よりも有望な改善を実現しているが、量子化とグラフの統合の可能性を完全には明らかにしていない。
グラフ構造は、検索における計算の無駄を引き起こすFastScanのバッチ内の性質を考慮して、共同で設計されていない。
本研究では,NGT-QGの後継として,量子化とグラフのよりシンフォニックな統合を実現するSymphonyQGという新しい手法を提案する。
実世界のデータセットに関する広範な実験に基づいて、SymphonyQGは、時間精度のトレードオフの観点から、新たな最先端技術を確立している。
関連論文リスト
- 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) - 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) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - A Comprehensive Study on Large-Scale Graph Training: Benchmarking and
Rethinking [124.21408098724551]
グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である
本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。
提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
論文 参考訳（メタデータ） (2022-10-14T03:43:05Z) - FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor
Search [20.928821121591493]
効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。
FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。
実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
論文 参考訳（メタデータ） (2022-06-22T22:30:46Z) - 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) - VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using
Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。
我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文 参考訳（メタデータ） (2021-10-27T11:48:50Z) - Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
ポイントクラウド上で学習するためのグラフ畳み込みネットワーク(GCN)の計算効率の向上を目指します。
一連の実験により、最適化されたネットワークは計算複雑性を減らし、メモリ消費を減らし、推論速度を加速した。
論文 参考訳（メタデータ） (2021-04-12T17:59:16Z) - A Quantum Graph Neural Network Approach to Particle Track Reconstruction [1.087475836765689]
本稿では,初期単純化ツリーネットワーク(TTN)モデルの低精度化を克服するために,反復的アプローチによる改良モデルを提案する。
我々は、量子コンピューティングの能力を活用して、非常に多くの状態を同時に評価し、それによって、大きなパラメータ空間を効果的に探索することを目指している。
論文 参考訳（メタデータ） (2020-07-14T07:25:24Z) - GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。
このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。
我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文 参考訳（メタデータ） (2020-02-08T10:03:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。