論文の概要: Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search

• arxiv url: http://arxiv.org/abs/2502.20695v1
• Date: Fri, 28 Feb 2025 04:03:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-03 13:40:13.434543
• Title: Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search
• Title（参考訳）: 10ビリオン規模のベクトル類似性探索のためのスケーラブルなオーバーロード対応グラフベースインデックス構築
• Authors: Yang Shi, Yiping Sun, Jiaolong Du, Xiaocheng Zhong, Zhiyong Wang, Yao Hu,
• Abstract要約: SOGAICは超大規模ベクトルデータベースに適したグラフベースのANNSインデックス構築システムである。 提案手法は実世界の産業用検索エンジンに導入され,毎日100億件以上のベクトルを処理している。
• 参考スコア（独自算出の注目度）: 18.419278931226756
• License:
• Abstract: Approximate Nearest Neighbor Search (ANNS) is essential for modern data-driven applications that require efficient retrieval of top-k results from massive vector databases. Although existing graph-based ANNS algorithms achieve a high recall rate on billion-scale datasets, their slow construction speed and limited scalability hinder their applicability to large-scale industrial scenarios. In this paper, we introduce SOGAIC, the first Scalable Overload-Aware Graph-Based ANNS Index Construction system tailored for ultra-large-scale vector databases: 1) We propose a dynamic data partitioning algorithm with overload constraints that adaptively introduces overlaps among subsets; 2) To enable efficient distributed subgraph construction, we employ a load-balancing task scheduling framework combined with an agglomerative merging strategy; 3) Extensive experiments on various datasets demonstrate a reduction of 47.3% in average construction time compared to existing methods. The proposed method has also been successfully deployed in a real-world industrial search engine, managing over 10 billion daily updated vectors and serving hundreds of millions of users.
• Abstract（参考訳）: 近似Nearest Neighbor Search (ANNS) は、大規模ベクトルデータベースからトップk結果の効率的な検索を必要とする現代のデータ駆動型アプリケーションに不可欠である。 既存のグラフベースのANNSアルゴリズムは、数十億のデータセット上で高いリコール率を達成するが、建設速度の遅さとスケーラビリティの制限により、大規模産業シナリオへの適用性が阻害される。 本稿では,超大規模ベクトルデータベースに適した,最初のスケーラブルオーバーロード対応グラフベースANNSインデックス構築システムであるSOGAICを紹介する。 1)サブセット間の重複を適応的に導入する過負荷制約付き動的データ分割アルゴリズムを提案する。 2)効率的な分散サブグラフ構築を実現するため,負荷分散タスクスケジューリングフレームワークと集約的マージ戦略を併用した。 3) 各種データセットの大規模な実験により, 既存手法と比較して平均工期が47.3%減少した。 提案手法は実世界の産業用検索エンジンにも適用され、1日あたり100億件以上の更新ベクターを管理し、数億人のユーザーにサービスを提供している。

関連論文リスト

• LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search [4.194768796374315]
  本稿では,内積近似が多出力回帰問題であることを示す観測に基づく新しい教師付きスコア計算法を提案する。 実験の結果,提案手法はクエリ待ち時間とメモリ使用量の両方においてPQよりも優れていることがわかった。 また,クラスタリングに基づくANNライブラリであるLoRANNを導入する。
  論文  参考訳（メタデータ） (2024-10-24T17:13:39Z)
• FusionLLM: A Decentralized LLM Training System on Geo-distributed GPUs with Adaptive Compression [55.992528247880685]
  分散トレーニングは、システム設計と効率に関する重要な課題に直面します。 大規模深層ニューラルネットワーク(DNN)のトレーニング用に設計・実装された分散トレーニングシステムFusionLLMを提案する。 本システムと手法は,収束性を確保しつつ,ベースライン法と比較して1.45～9.39倍の高速化を実現可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-16T16:13:19Z)
• RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search [11.069814476661827]
  クロスモーダルANNSは、あるモダリティからデータベクトルを使用して、他のモダリティから最も類似したアイテムを検索することを目的としている。 最先端のANNSアプローチでは、OODワークロードのパフォーマンスが低下している。 本稿では、クエリ分布のガイダンスに基づいて構築された効率的なANNSグラフインデックスであるpRojected bipartite Graph(RoarGraph)を提案する。
  論文  参考訳（メタデータ） (2024-08-16T06:48:16Z)
• Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation [20.409659920455955]
  近似k-Nearest Neighbour (ANN) 法は情報マイニングや大規模高次元データセットでの機械学習支援によく用いられる。 静的なデータセットを持つアプリケーションでは、ランタイム制約とデータセットプロパティを使用して、適切な操作特性を持つANNメソッドを経験的に選択することができる。 従来の評価手法は、インデックス構造を更新する際の計算コストや、インデックス更新の率とサイズを考慮していない。
  論文  参考訳（メタデータ） (2024-04-30T06:21:44Z)
• Efficient Architecture Search via Bi-level Data Pruning [70.29970746807882]
  この研究は、DARTSの双方向最適化におけるデータセット特性の重要な役割を探求する先駆者となった。 我々は、スーパーネット予測力学を計量として活用する新しいプログレッシブデータプルーニング戦略を導入する。 NAS-Bench-201サーチスペース、DARTSサーチスペース、MobileNetのようなサーチスペースに関する総合的な評価は、BDPがサーチコストを50%以上削減することを検証する。
  論文  参考訳（メタデータ） (2023-12-21T02:48:44Z)
• KAPLA: Pragmatic Representation and Fast Solving of Scalable NN Accelerator Dataflow [0.0]
  汎用的で最適化され、高速なデータフロー解決器KAPLAを構築し、効果的な妥当性チェックと効率推定により設計空間を探索する。 KAPLAは、トレーニングと推論のための結果データフローにおいて、わずか2.2%と7.7%のエネルギーオーバーヘッドしか達成していない。 また、ランダムおよび機械学習ベースのアプローチよりも優れており、より最適化された結果と桁違いに高速な検索スピードアップを実現している。
  論文  参考訳（メタデータ） (2023-06-09T03:12:42Z)
• 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)
• Arch-Graph: Acyclic Architecture Relation Predictor for Task-Transferable Neural Architecture Search [96.31315520244605]
  Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。 Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。 わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
  論文  参考訳（メタデータ） (2022-04-12T16:46:06Z)
• Augmenting Novelty Search with a Surrogate Model to Engineer Meta-Diversity in Ensembles of Classifiers [5.8497361730688695]
  行動多様性を促進するために神経進化とノベルティ検索を組み合わせることで、分類のための高性能なアンサンブルを構築することができる。 本稿では,2つのニューラルネットワークアーキテクチャ間の挙動距離を推定する代理モデルを用いて,この制限を克服する手法を提案する。
  論文  参考訳（メタデータ） (2022-01-30T19:13:32Z)
• ZARTS: On Zero-order Optimization for Neural Architecture Search [94.41017048659664]
  微分可能なアーキテクチャサーチ (DARTS) は、NASの高効率性のため、一般的なワンショットパラダイムである。 この作業はゼロオーダーの最適化に変わり、上記の近似を強制せずに探索するための新しいNASスキームであるZARTSを提案する。 特に、12ベンチマークの結果は、DARTSの性能が低下するZARTSの顕著な堅牢性を検証する。
  論文  参考訳（メタデータ） (2021-10-10T09:35:15Z)
• MS-RANAS: Multi-Scale Resource-Aware Neural Architecture Search [94.80212602202518]
  我々は,MS-RANAS(Multi-Scale Resource-Aware Neural Architecture Search)を提案する。 我々は,検索コストの削減を図るために,ワンショットのアーキテクチャ探索手法を採用した。 我々は精度-速度トレードオフの観点から最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-09-29T11:56:01Z)

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

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