論文の概要: CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2509.00365v1
• Date: Sat, 30 Aug 2025 05:27:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 15:17:03.196687
• Title: CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search
• Title（参考訳）: CRouting:グラフベースの近似近傍検索における余剰距離の削減
• Authors: Zhenxin Li, Shuibing He, Jiahao Guo, Xuechen Zhang, Xian-He Sun, Gang Chen,
• Abstract要約: 近似近接探索(ANNS)は、情報検索とAIアプリケーションにおいて重要な問題である。 本稿では,不必要な距離計算をバイパスするCRoutingという新しいルーティング手法を提案する。 実験により、CRoutingは、最大41.5%までの距離計算を削減し、2つの主要なグラフインデックス上で、毎秒1.48$times$までクエリを高速化することを示した。
• 参考スコア（独自算出の注目度）: 9.557937699715124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate nearest neighbor search (ANNS) is a crucial problem in information retrieval and AI applications. Recently, there has been a surge of interest in graph-based ANNS algorithms due to their superior efficiency and accuracy. However, the repeated computation of distances in high-dimensional spaces constitutes the primary time cost of graph-based methods. To accelerate the search, we propose a novel routing strategy named CRouting, which bypasses unnecessary distance computations by exploiting the angle distributions of high-dimensional vectors. CRouting is designed as a plugin to optimize existing graph-based search with minimal code modifications. Our experiments show that CRouting reduces the number of distance computations by up to 41.5% and boosts queries per second by up to 1.48$\times$ on two predominant graph indexes, HNSW and NSG. Code is publicly available at https://github.com/ISCS-ZJU/CRouting.
• Abstract（参考訳）: 近似近接探索(ANNS)は、情報検索とAIアプリケーションにおいて重要な問題である。 近年,グラフに基づくANNSアルゴリズムへの関心が高まっている。 しかし、高次元空間における距離の繰り返し計算は、グラフベースの手法の一次時間コストを構成する。 探索を高速化するために,高次元ベクトルの角度分布を利用して不必要な距離計算をバイパスするCRoutingという新しいルーティング手法を提案する。 CRoutingは、最小限のコード修正で既存のグラフベースの検索を最適化するプラグインとして設計されている。 実験の結果、CRoutingは、最大41.5%までの距離計算を削減し、HNSWとNSGの2つの主要なグラフインデックス上で、1秒あたりのクエリを最大1.48$\times$に向上させることがわかった。 コードはhttps://github.com/ISCS-ZJU/CRouting.comで公開されている。

関連論文リスト

• 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)
• SpirDet: Towards Efficient, Accurate and Lightweight Infrared Small Target Detector [60.42293239557962]
  我々は、赤外線小ターゲットの効率的な検出のための新しいアプローチであるSpirDetを提案する。 新しいデュアルブランチスパースデコーダを用いて特徴写像を復元する。 大規模な実験により、提案されたSpirDetは最先端モデルよりも大幅に優れていることが示された。
  論文  参考訳（メタデータ） (2024-02-08T05:06:14Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  クロスエンコーダモデルは、直接k-nearest neighbor(k-NN)サーチには不当に高価である。 本稿では,現実的に重要なトップk近傍の近似誤差を適応的に,反復的に,効率的に最小化するADACURを提案する。
  論文  参考訳（メタデータ） (2023-05-04T17:01:17Z)
• 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)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  ポイントクラウド上で学習するためのグラフ畳み込みネットワーク(GCN)の計算効率の向上を目指します。 一連の実験により、最適化されたネットワークは計算複雑性を減らし、メモリ消費を減らし、推論速度を加速した。
  論文  参考訳（メタデータ） (2021-04-12T17:59:16Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)

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

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