論文の概要: Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization

• arxiv url: http://arxiv.org/abs/2501.13992v1
• Date: Thu, 23 Jan 2025 10:20:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-27 14:57:59.779871
• Title: Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization
• Title（参考訳）: スキップブリッジを用いたデュアルブランチHNSWアプローチとLID駆動最適化
• Authors: Hy Nguyen, Nguyen Hung Nguyen, Nguyen Linh Bao Nguyen, Srikanth Thudumu, Hung Du, Rajesh Vasa, Kon Mouzakis,
• Abstract要約: Hierarchical Navigable Small World (HNSW)アルゴリズムは近接探索に広く利用されている。 提案手法は, 局所最適化とクラスタ切断を緩和し, 建設速度を向上し, 推論速度を向上するアルゴリズムである。 様々なベンチマークとデータセットの実験により、我々のアルゴリズムは元のHNSWを精度と速度の両方で上回っていることがわかった。
• 参考スコア（独自算出の注目度）: 0.8786066051474574
• License:
• Abstract: The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor (ANN) search, leveraging the principles of navigable small-world graphs. However, it faces some limitations. The first is the local optima problem, which arises from the algorithm's greedy search strategy, selecting neighbors based solely on proximity at each step. This often leads to cluster disconnections. The second limitation is that HNSW frequently fails to achieve logarithmic complexity, particularly in high-dimensional datasets, due to the exhaustive traversal through each layer. To address these limitations, we propose a novel algorithm that mitigates local optima and cluster disconnections while enhancing the construction speed, maintaining inference speed. The first component is a dual-branch HNSW structure with LID-based insertion mechanisms, enabling traversal from multiple directions. This improves outlier node capture, enhances cluster connectivity, accelerates construction speed and reduces the risk of local minima. The second component incorporates a bridge-building technique that bypasses redundant intermediate layers, maintaining inference and making up the additional computational overhead introduced by the dual-branch structure. Experiments on various benchmarks and datasets showed that our algorithm outperforms the original HNSW in both accuracy and speed. We evaluated six datasets across Computer Vision (CV), and Natural Language Processing (NLP), showing recall improvements of 18\% in NLP, and up to 30\% in CV tasks while reducing the construction time by up to 20\% and maintaining the inference speed. We did not observe any trade-offs in our algorithm. Ablation studies revealed that LID-based insertion had the greatest impact on performance, followed by the dual-branch structure and bridge-building components.
• Abstract（参考訳）: Hierarchical Navigable Small World (HNSW) アルゴリズムは、ナビゲート可能な小世界グラフの原理を活かして、近接した近傍(ANN)探索に広く利用されている。 しかし、いくつかの制限がある。 1つは局所最適問題であり、これはアルゴリズムの欲求探索戦略から生じ、各ステップにのみ近接して隣人を選択する。 これはしばしばクラスタの切断につながる。 第2の制限は、HNSWは、特に高次元データセットにおいて、各層を通る徹底的なトラバースのために、対数複雑性を頻繁に達成できないことである。 これらの制約に対処するため,提案手法では,局所的な最適化とクラスタ切断を緩和し,建設速度を向上し,推論速度を向上するアルゴリズムを提案する。 第1のコンポーネントは、LIDベースの挿入機構を備えたデュアルブランチHNSW構造であり、複数の方向からの移動を可能にする。 これにより、outlierノードキャプチャを改善し、クラスタ接続を改善し、構築速度を加速し、ローカルミニマのリスクを低減する。 第2のコンポーネントは、冗長な中間層をバイパスし、推論を維持し、デュアルブランチ構造によって導入された計算オーバーヘッドを補うブリッジ構築技術を含んでいる。 様々なベンチマークとデータセットの実験により、我々のアルゴリズムは元のHNSWを精度と速度の両方で上回っていることがわかった。 我々は,コンピュータビジョン(CV)と自然言語処理(NLP)の6つのデータセットを評価し,NLPの18倍,CVタスクの最大30倍,建設時間を最大20倍に削減し,推論速度の維持を図った。 私たちはアルゴリズムのトレードオフを観察しませんでした。 アブレーション試験により, LIDをベースとした挿入が性能に最も大きな影響を与え, 次いで二重分岐構造と橋梁構造が認められた。

関連論文リスト

• HAIL: An Efficient Iterative Algorithm for Qubit Mapping via Layer-Weight Assignment and Search Space Reduction [7.698997402561804]
  現在の量子デバイスは物理的量子ビットと限られた数の隣接する量子ビット間の相互作用しかサポートしていない。 回路を実行するには、キュービット間のマッピング関係を調整するためにSWAPゲートを挿入する必要がある。 本稿では,新たなSWAPゲートを最小化するための効率的な反復量子ビットマッピングアルゴリズムであるHAILを提案する。
  論文  参考訳（メタデータ） (2025-02-11T13:21:33Z)
• Simple Contrastive Graph Clustering [41.396185271303956]
  既存の手法を改善するための単純なコントラストグラフクラスタリング(SCGC)アルゴリズムを提案する。 我々のアルゴリズムは、最近のコントラストの高いディープクラスタリング競合よりも、平均して7倍のスピードアップを達成している。
  論文  参考訳（メタデータ） (2022-05-11T06:45:19Z)
• A density peaks clustering algorithm with sparse search and K-d tree [16.141611031128427]
  この問題を解決するために,スパース探索とK-d木を用いた密度ピーククラスタリングアルゴリズムを開発した。 分散特性が異なるデータセット上で、他の5つの典型的なクラスタリングアルゴリズムと比較して実験を行う。
  論文  参考訳（メタデータ） (2022-03-02T09:29:40Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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