論文の概要: Slipstream: Locality-Aware Graph Index Construction for Streaming Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2606.02992v1
• Date: Tue, 02 Jun 2026 00:59:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:04.66591
• Title: Slipstream: Locality-Aware Graph Index Construction for Streaming Approximate Nearest Neighbor Search
• Title（参考訳）: Slipstream: 近傍探索のストリーミングのための局所性を考慮したグラフインデックス構築
• Authors: Shubing Yang, Dongfang Zhao,
• Abstract要約: 本稿では,ANNSのグラフインデックスにおける頻繁な挿入の計算コストを大幅に削減する新しい手法であるSlipstreamを提案する。 Slipstreamの中核的なアイデアは、ベクターストリームの連続性を利用することだ。 実験の結果,Slipstreamのスループットはベースラインよりも30.8$times$高いことがわかった。
• 参考スコア（独自算出の注目度）: 0.7770535067924795
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph indexes are widely used for high-recall approximate nearest neighbor search (ANNS), but many real-time applications require streaming ANNS. In these real-time applications, continuously arriving embeddings must search the existing graph for candidate neighbors before updating graph edges, which makes repeated index construction a bottleneck for streaming ingestion workloads. We propose Slipstream, a new method that significantly reduces the computational cost of frequent insertions in graph indexes for ANNS. The core idea of Slipstream is exploiting the continuity in vector streams: the newly arrived point starts from promising candidates found during the previous insertion rather than searching from the entry point. More technically, Slipstream evaluates distinct subsets of starting candidates followed by an adaptive controller that narrows or widens the range according to the stream's stability. We further show that Slipstream is beyond heuristic: We derive an abstract model to characterize Slipstream's performance and analyze its theoretical bounds. We have implemented Slipstream in two popular open-source libraries (Faiss, HNSWLib) and compared it with four baseline methods on five streaming vector datasets. Experimental results show that Slipstream achieves up to 30.8$\times$ higher end-to-end throughput than baselines while maintaining at least 0.95 recall@10.
• Abstract（参考訳）: グラフインデックスはANNS (High-Recall Near Near Near Search) に広く使われているが、多くのリアルタイムアプリケーションはANNSをストリーミングする必要がある。 これらのリアルタイムアプリケーションでは、グラフエッジを更新する前に、着信した埋め込みが既存のグラフを検索しなければなりません。 本稿では,ANNSのグラフインデックスにおける頻繁な挿入の計算コストを大幅に削減する新しい手法であるSlipstreamを提案する。 Slipstreamの中核的な考え方は、ベクトルストリームの連続性を利用しており、新しく到着したポイントは、エントリポイントから検索するのではなく、前回の挿入で見つかる有望な候補から始まる。 より技術的には、Slipstreamは開始候補の異なるサブセットを評価し、その後にストリームの安定性に応じて範囲を狭めたり広げたりする適応制御器が続く。 我々は,Slipstreamの性能を解析し,その理論的境界を解析するための抽象モデルを導出する。 我々はSlipstreamを2つの人気のあるオープンソースライブラリ(Faiss, HNSWLib)で実装し、5つのストリーミングベクトルデータセット上の4つのベースライン手法と比較した。 実験の結果、Slipstreamはベースラインよりも最大30.8$\times$高いエンドツーエンドスループットを実現し、少なくとも0.95リコール@10を維持していることがわかった。

関連論文リスト

• Curator: Efficient Vector Search with Low-Selectivity Filters [12.774238654446032]
  グラフベースのインデックスは、未フィルタリングANNSでは最先端のパフォーマンスを実現するが、低選択性フィルタリングクエリでは接続性の低下に遭遇する。 近年の研究では、グラフ度を拡大することでこの問題に対処するグラフインデックスが提案されている。 低選択性フィルタANNSに対する既存のグラフベースのアプローチを補完する分割型インデックスであるCuratorを提案する。
  論文  参考訳（メタデータ） (2026-01-03T21:35:01Z)
• CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search [9.557937699715124]
  近似近接探索(ANNS)は、情報検索とAIアプリケーションにおいて重要な問題である。 本稿では,不必要な距離計算をバイパスするCRoutingという新しいルーティング手法を提案する。 実験により、CRoutingは、最大41.5%までの距離計算を削減し、2つの主要なグラフインデックス上で、毎秒1.48$times$までクエリを高速化することを示した。
  論文  参考訳（メタデータ） (2025-08-30T05:27:09Z)
• Sublinear Space Graph Algorithms in the Continual Release Model [48.65946341463292]
  我々は,非プライベートなストリーミングと静的アルゴリズムからスペーシフィケーション手法を新たに利用して,サブ線形空間における新たな結果,連続的なリリース設定を実現する。 これには、最も高密度な部分グラフのためのアルゴリズム、最大マッチング、および最初の連続リリース$k$-core分解アルゴリズムが含まれる。
  論文  参考訳（メタデータ） (2024-07-24T20:15:07Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)

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

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