論文の概要: Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation

• arxiv url: http://arxiv.org/abs/2407.07871v2
• Date: Mon, 15 Jul 2024 14:23:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-10 19:45:58.497900
• Title: Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation
• Title（参考訳）: リアルタイム更新のためのHNSWインデックスの強化:到達不能な点と性能劣化に対処する
• Authors: Wentao Xiao, Yueyang Zhan, Rui Xi, Mengshu Hou, Jianming Liao,
• Abstract要約: グラフベースのインデックスは、大量のリアルタイム削除、挿入、更新に直面したとき、受け入れられなくなる。 本稿では,HNSWの欠点を克服するための効率的な対策について述べる。 提案したMN-RUアルゴリズムは,更新効率を効果的に向上し,到達不能な点の成長速度を抑え,全体の性能を向上し,グラフの完全性を維持する。
• 参考スコア（独自算出の注目度）: 0.9592510017131104
• License:
• Abstract: The approximate nearest neighbor search (ANNS) is a fundamental and essential component in data mining and information retrieval, with graph-based methodologies demonstrating superior performance compared to alternative approaches. Extensive research efforts have been dedicated to improving search efficiency by developing various graph-based indices, such as HNSW (Hierarchical Navigable Small World). However, the performance of HNSW and most graph-based indices become unacceptable when faced with a large number of real-time deletions, insertions, and updates. Furthermore, during update operations, HNSW can result in some data points becoming unreachable, a situation we refer to as the `unreachable points phenomenon'. This phenomenon could significantly affect the search accuracy of the graph in certain situations. To address these issues, we present efficient measures to overcome the shortcomings of HNSW, specifically addressing poor performance over long periods of delete and update operations and resolving the issues caused by the unreachable points phenomenon. Our proposed MN-RU algorithm effectively improves update efficiency and suppresses the growth rate of unreachable points, ensuring better overall performance and maintaining the integrity of the graph. Our results demonstrate that our methods outperform existing approaches. Furthermore, since our methods are based on HNSW, they can be easily integrated with existing indices widely used in the industrial field, making them practical for future real-world applications. Code is available at \url{https://github.com/xwt1/MN-RU.git}
• Abstract（参考訳）: 近似近接探索(ANNS)は,データマイニングや情報検索において基本的かつ不可欠な要素であり,グラフベースの手法は,代替手法よりも優れた性能を示す。 HNSW(Hierarchical Navigable Small World)などのグラフベースの指標を開発することにより,探索効率の向上に重点が置かれている。 しかし、HNSWとほとんどのグラフベースのインデックスは、大量のリアルタイム削除、挿入、更新に直面すると受け入れられなくなる。 さらに、更新操作中、HNSWはいくつかのデータポイントが到達不能になる可能性がある。 この現象は特定の状況下でのグラフの探索精度に大きな影響を及ぼす可能性がある。 これらの課題に対処するため,HNSWの欠点を克服するための効率的な対策として,削除操作と更新操作の長期にわたるパフォーマンスの低下と,到達不能な点現象による問題の解決について述べる。 提案したMN-RUアルゴリズムは,更新効率を効果的に向上し,到達不能な点の成長速度を抑え,全体の性能を向上し,グラフの完全性を維持する。 提案手法が既存手法より優れていることを示す。 さらに,本手法はHNSWをベースとしているため,産業分野で広く使用されている既存の指標と容易に統合することができ,将来的な実世界の応用に有効である。 コードは \url{https://github.com/xwt1/MN-RU.git} で入手できる。

関連論文リスト

• In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search [12.092920351505036]
  IP-DiskANNは,挿入処理と削除処理を効率よく行うことにより,バッチ統合を回避する最初のアルゴリズムである。 ハイリコールとローリコールの両方で、様々な長い更新パターンに対して安定したリコールを行う。
  論文  参考訳（メタデータ） (2025-02-19T15:41:08Z)
• FIT-GNN: Faster Inference Time for GNNs Using Coarsening [1.323700980948722]
  粗大化に基づく手法は、グラフをより小さなグラフに減らし、より高速な計算をもたらす。 従来の研究は、推論フェーズにおける計算コストに十分な対処を行っていなかった。 本稿では,GNNの学習と推論の両段階における計算負担を軽減することにより,GNNのスケーラビリティを向上させる新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-10-19T06:27:24Z)
• Haste Makes Waste: A Simple Approach for Scaling Graph Neural Networks [37.41604955004456]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において顕著な成功を収めている。 GNNを大規模グラフのアプリケーションに拡張するための様々なサンプリング手法が提案されている。
  論文  参考訳（メタデータ） (2024-10-07T18:29:02Z)
• CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with Dynamic Data Ingestion [8.036012885171166]
  我々は、動的データ取り込みを伴う連続近似Nearest Neighbor Searchに適したベンチマークであるCANDYを紹介する。 CANDYは幅広いAKNNアルゴリズムを包括的に評価し、機械学習駆動推論のような高度な最適化を統合する。 多様なデータセットに対する評価では、より単純なAKNNベースラインが、リコールやレイテンシの点で、より複雑な選択肢を上回ることが示されている。
  論文  参考訳（メタデータ） (2024-06-28T04:46:11Z)
• OCDB: Revisiting Causal Discovery with a Comprehensive Benchmark and Evaluation Framework [21.87740178652843]
  因果発見は透明性と信頼性を改善するための有望なアプローチを提供する。 本稿では,因果構造と因果効果の違いを評価するための指標を用いたフレキシブルな評価フレームワークを提案する。 実データに基づくOpen Causal Discovery Benchmark (OCDB)を導入し、公正な比較を促進し、アルゴリズムの最適化を促進する。
  論文  参考訳（メタデータ） (2024-06-07T03:09:22Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection [65.24854366973794]
  ノードレベルのグラフ異常検出(GAD)は、医学、ソーシャルネットワーク、eコマースなどの分野におけるグラフ構造化データから異常ノードを特定する上で重要な役割を果たす。 本稿では,GADの効率を向上させるために,PREM (preprocessing and Matching) という簡単な手法を提案する。 我々のアプローチは、強力な異常検出機能を維持しながら、GADを合理化し、時間とメモリ消費を削減します。
  論文  参考訳（メタデータ） (2023-10-18T02:59:57Z)
• 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)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  グラフの外れ値検出は、多くのアプリケーションにおいて、新しいが重要な機械学習タスクである。 UNODと呼ばれるグラフに対して、最初の包括的教師なしノード外乱検出ベンチマークを示す。
  論文  参考訳（メタデータ） (2022-06-21T01:46:38Z)
• Optimizing for the Future in Non-Stationary MDPs [52.373873622008944]
  本稿では,今後の性能予測を最大化するポリシ勾配アルゴリズムを提案する。 我々のアルゴリズムであるPrognosticatorは2つのオンライン適応手法よりも非定常性に頑健であることを示す。
  論文  参考訳（メタデータ） (2020-05-17T03:41:19Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。 GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。 我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-25T15:17:58Z)

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

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