論文の概要: 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} で入手できる。

関連論文リスト

• 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)
• Gradient Transformation: Towards Efficient and Model-Agnostic Unlearning for Dynamic Graph Neural Networks [66.70786325911124]
  グラフアンラーニングは、ユーザのプライバシ保護と、望ましくないデータによるネガティブな影響軽減に不可欠なツールとして登場した。 DGNNの普及に伴い、動的グラフアンラーニングの実装を検討することが不可欠となる。 DGNNアンラーニングを実装するために,効率的,効率的,モデルに依存しない,事後処理手法を提案する。
  論文  参考訳（メタデータ） (2024-05-23T10:26:18Z)
• 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)
• Less Can Be More: Unsupervised Graph Pruning for Large-scale Dynamic Graphs [42.864057751606616]
  動的グラフ上での教師なしグラフプルーニングの問題を提案し,検討する。 提案するSTEPフレームワークは,入力動的グラフから潜在的に冗長なエッジを取り除くことを学習する。 実世界の3つのデータセットに対する我々の結果は、GNNの有効性、堅牢性、効率性を改善する利点を実証している。
  論文  参考訳（メタデータ） (2023-05-18T03:23:53Z)
• Fast and Attributed Change Detection on Dynamic Graphs with Density of States [9.409281517596396]
  現在のソリューションは、大規模な実世界のグラフに対してうまくスケールせず、大量のノードの追加/削除に対する堅牢性がなく、ノード属性の変更を見落としている。 SCPDは,各ステップにおけるラプラシアスペクトルの分布を効率よく近似することにより,各グラフスナップショットに対する埋め込みを生成する。 SCPDは最先端の性能を実現し,数分間で数百万のエッジを容易に処理できることを示す。
  論文  参考訳（メタデータ） (2023-05-15T16:02:36Z)
• 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)

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

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