Fugu-MT 論文翻訳(概要): CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search

論文の概要: CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search

arxiv url: http://arxiv.org/abs/2507.19802v1
Date: Sat, 26 Jul 2025 05:27:32 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-29 16:23:56.26112
Title: CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search
Title（参考訳）: CleANN:グラフベースの近似近傍探索における効率的な完全ダイナミズム
Authors: Ziyu Zhang, Yuanhao Wei, Joshua Engels, Julian Shun,
Abstract要約: 近似近接探索(ANNS)は、AIワークロードのための様々な基礎データタスクにおいて、重要なアルゴリズム問題となっている。既存のグラフベースのインデックスは静的シナリオのために設計されている。 CleANNは完全なダイナミズムの下で品質を維持しながら、そのような効率を達成する最初のANNSインデックスである。
参考スコア（独自算出の注目度）: 6.319134122855477
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Approximate nearest neighbor search (ANNS) has become a quintessential algorithmic problem for various other foundational data tasks for AI workloads. Graph-based ANNS indexes have superb empirical trade-offs in indexing cost, query efficiency, and query approximation quality. Most existing graph-based indexes are designed for the static scenario, where there are no updates to the data after the index is constructed. However, full dynamism (insertions, deletions, and searches) is crucial to providing up-to-date responses in applications using vector databases. It is desirable that the index efficiently supports updates and search queries concurrently. Existing dynamic graph-based indexes suffer from at least one of the following problems: (1) the query quality degrades as updates happen; and (2) the graph structure updates used to maintain the index quality upon updates are global and thus expensive. To solve these problems, we propose the CleANN system which consists of three main components: (1) workload-aware linking of diverse search tree descendants to combat distribution shift; (2)query-adaptive on-the-fly neighborhood consolidation to efficiently handle deleted nodes; and (3) semi-lazy memory cleaning to clean up stale information in the data structure and reduce the work spent by the first two components. We evaluate CleANN on 7 diverse datasets on fully dynamic workloads and find that CleANN has query quality at least as good as if the index had been built statically using the corresponding data. In the in-memory setting using 56 hyper-threads, with all types of queries running concurrently, at the same recall level, CleANN achieves 7-1200x throughput improvement on million-scale real-world datasets. To the best of our knowledge, CleANN is the first concurrent ANNS index to achieve such efficiency while maintaining quality under full dynamism.
Abstract（参考訳）: 近似近接探索(ANNS)は、AIワークロードのための様々な基礎データタスクにおいて、重要なアルゴリズム問題となっている。グラフベースのANNSインデックスは、インデックス作成コスト、クエリ効率、クエリ近似品質において、非常に経験的なトレードオフがある。既存のグラフベースのインデックスは静的シナリオのために設計されている。しかし、完全なダイナミズム(慣例、削除、検索)は、ベクトルデータベースを使用したアプリケーションに最新の応答を提供するために不可欠である。インデックスは、更新と検索クエリを同時に効率的にサポートすることが望ましい。既存の動的グラフベースのインデックスは,(1) クエリ品質が更新時に低下する,(2) 更新時にインデックス品質を維持するために使用されるグラフ構造更新はグローバルで高価である,という問題の少なくとも1つに悩まされている。これらの問題を解決するために,(1)多種多様な探索木の子孫を戦闘分散シフトにリンクする作業負荷認識システム,(2)削除ノードを効率的に処理するためのクエリ適応型オンザフライ地区統合,(3)データ構造中の古い情報をクリーンアップし,最初の2つのコンポーネントが使用する作業を減らす半遅延メモリクリーニングという3つの主要コンポーネントからなるCleANNシステムを提案する。我々はCleANNをフルダイナミックなワークロード上で7つの多様なデータセット上で評価し、CleANNがクエリ品質を少なくとも、対応するデータを使って静的に構築されたかのように評価する。 56のハイパースレッドを使用したインメモリ設定では、あらゆる種類のクエリが同時に同じリコールレベルで実行され、CleANNは100万規模の実世界のデータセットで7-1200倍のスループット向上を実現している。我々の知る限りでは、CleANNは完全なダイナミズムの下で品質を維持しながら、そのような効率を達成する最初の同時ANNSインデックスである。

関連論文リスト

Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities [19.352675865525395]
本稿では,Adaptive Topology とQuery AwarEness を用いた GATE, High-tier Near Graph を提案する。 Gateは、最先端のグラフベースのインデックスと比較して、クエリパフォーマンスの1.2-2.0倍の高速化を実現している。
論文参考訳（メタデータ） (2025-06-19T03:07:12Z)
HAKES: Scalable Vector Database for Embedding Search Service [16.034584281180006]
我々は,並列な読み書きワークロード下で高いスループットと高いリコールを実現するベクトルデータベースを構築した。我々のインデックスは、高リコール領域と同時読み書きワークロード下でインデックスベースラインより優れています。 nameysはスケーラブルで、ベースラインよりも最大16タイムで高いスループットを実現します。
論文参考訳（メタデータ） (2025-05-18T19:26:29Z)
In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search [12.092920351505036]
IP-DiskANNは,挿入処理と削除処理を効率よく行うことにより,バッチ統合を回避する最初のアルゴリズムである。ハイリコールとローリコールの両方で、様々な長い更新パターンに対して安定したリコールを行う。
論文参考訳（メタデータ） (2025-02-19T15:41:08Z)
Semi-Parametric Retrieval via Binary Bag-of-Tokens Index [71.78109794895065]
SemI-parametric Disentangled Retrieval (SiDR)は、ニューラルパラメータから検索インデックスを分離するバイエンコーダ検索フレームワークである。 SiDRは、検索のための非パラメトリックトークン化インデックスをサポートし、BM25のようなインデックス化の複雑さを著しく改善した。
論文参考訳（メタデータ） (2024-05-03T08:34:13Z)
Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation [20.409659920455955]
近似k-Nearest Neighbour (ANN) 法は情報マイニングや大規模高次元データセットでの機械学習支援によく用いられる。静的なデータセットを持つアプリケーションでは、ランタイム制約とデータセットプロパティを使用して、適切な操作特性を持つANNメソッドを経験的に選択することができる。従来の評価手法は、インデックス構造を更新する際の計算コストや、インデックス更新の率とサイズを考慮していない。
論文参考訳（メタデータ） (2024-04-30T06:21:44Z)
LIST: Learning to Index Spatio-Textual Data for Embedding based Spatial Keyword Queries [53.843367588870585]
リスト K-kNN 空間キーワードクエリ (TkQ) は、空間的およびテキスト的関連性の両方を考慮したランキング関数に基づくオブジェクトのリストを返す。効率的かつ効率的な指標、すなわち高品質なラベルの欠如とバランスの取れない結果を構築する上で、大きな課題が2つある。この2つの課題に対処する新しい擬似ラベル生成手法を開発した。
論文参考訳（メタデータ） (2024-03-12T05:32:33Z)
On Exploring Node-feature and Graph-structure Diversities for Node Drop Graph Pooling [86.65151066870739]
現在のノードドロッププーリング法は、ノードの特徴やグラフ構造の観点からグラフの多様性を無視し、結果としてグラフレベル以下の表現をもたらす。そこで本稿では,textiti.fltextbfIpscore と textbfDropscore の2つの操作を持つ textbfMulti スコア空間からなる MID を新たに提案する。具体的には、多次元スコア空間は、複数の基準を通してノードの重要さを描いており、フリップスコアは異種ノードの維持を奨励している。
論文参考訳（メタデータ） (2023-06-22T08:02:01Z)
OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries [8.950168559003993]
Approximate Nearest Neighbor Search (ANNS)の最先端アルゴリズムは、インデックスデータ分布にオーバーフィットすることで、データに依存したインデックスを構築する。 OOD-DiskANNはOODクエリのスペーリングサンプル(インデックスセットサイズの1%)を使用し、同じメモリフットプリントのSoTAアルゴリズムに対して、平均クエリレイテンシを最大40%改善する。
論文参考訳（メタデータ） (2022-10-22T21:22:50Z)
End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
Extreme Multi-label Classification (XMC) は現実世界の問題を解決するための一般的なフレームワークである。本稿では,木系インデックスを特殊重み付きグラフベースインデックスに緩和する新しい手法を提案する。 ELIASは、数百万のラベルを持つ大規模極端分類ベンチマークで最先端のパフォーマンスを達成する。
論文参考訳（メタデータ） (2022-10-16T01:34:17Z)
QD-GCN: Query-Driven Graph Convolutional Networks for Attributed Community Search [54.42038098426504]
QD-GCNは、ACS問題を解決するために、コミュニティ構造とノード属性を統一するエンドツーエンドフレームワークである。本稿では、QD-GCNが既存の属性付きコミュニティ検索アルゴリズムを効率性と有効性の両方で上回ることを示す。
論文参考訳（メタデータ） (2021-04-08T07:52:48Z)
IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文参考訳（メタデータ） (2021-03-17T23:13:25Z)
The Case for Learned Spatial Indexes [62.88514422115702]
我々は、空間範囲の問合せに答えるために、最先端の学習した多次元インデックス構造(すなわちFlood)から提案した手法を用いる。 i) パーティション内の機械学習検索は、1次元でフィルタリングを使用する場合の2進探索よりも11.79%速く、39.51%高速であることを示す。また、2次元でフィルタする最も近い競合相手の1.23倍から1.83倍の速さで機械学習インデックスを精査する。
論文参考訳（メタデータ） (2020-08-24T12:09:55Z)

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

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