論文の概要: SIEVE: Effective Filtered Vector Search with Collection of Indexes

• arxiv url: http://arxiv.org/abs/2507.11907v2
• Date: Sun, 20 Jul 2025 04:50:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-22 12:28:43.151556
• Title: SIEVE: Effective Filtered Vector Search with Collection of Indexes
• Title（参考訳）: SIEVE: インデックスのコレクションによる効率的なフィルタベクター検索
• Authors: Zhaoheng Li, Silu Huang, Wei Ding, Yongjoo Park, Jianjun Chen,
• Abstract要約: 子供タグで動画を推薦するといった現実世界のタスクは、ハードな述語に関連する最も類似したベクターを見つけるために削減できる。 従来の最先端のグラフベース類似性探索技術は、厳しい制約を考慮すると急速に退化する。 選択性や形態の異なるデータセットに対して,優れた性能とサポートを示す。
• 参考スコア（独自算出の注目度）: 11.81573028534193
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many real-world tasks such as recommending videos with the kids tag can be reduced to finding most similar vectors associated with hard predicates. This task, filtered vector search, is challenging as prior state-of-the-art graph-based (unfiltered) similarity search techniques quickly degenerate when hard constraints are considered. That is, effective graph-based filtered similarity search relies on sufficient connectivity for reaching the most similar items within just a few hops. To consider predicates, recent works propose modifying graph traversal to visit only the items that may satisfy predicates. However, they fail to offer the just-a-few-hops property for a wide range of predicates: they must restrict predicates significantly or lose efficiency if only a small fraction of items satisfy predicates. We propose an opposite approach: instead of constraining traversal, we build many indexes each serving different predicate forms. For effective construction, we devise a three-dimensional analytical model capturing relationships among index size, search time, and recall, with which we follow a workload-aware approach to pack as many useful indexes as possible into a collection. At query time, the analytical model is employed yet again to discern the one that offers the fastest search at a given recall. We show superior performance and support on datasets with varying selectivities and forms: our approach achieves up to 8.06x speedup while having as low as 1% build time versus other indexes, with less than 2.15x memory of a standard HNSW graph and modest knowledge of past workloads.
• Abstract（参考訳）: 子供タグで動画を推薦するといった現実世界の多くのタスクは、ハードな述語に関連する最も類似したベクターを見つけるために削減できる。 厳密な制約を考慮すれば,従来のグラフに基づく(フィルタされていない)類似性検索技術は急速に劣化するので,この課題はベクトル探索のフィルタリングが困難である。 つまり、グラフベースのフィルタリング類似性検索は、ほんの数ホップで最も類似したアイテムに到達するのに十分な接続性に依存している。 述語を考えるために、近年の研究では、述語を満たす可能性のある項目のみを訪問するためにグラフトラバーサルを変更することを提案する。 しかし、彼らは幅広い述語に対してJust-a-few-hopsプロパティを提供することができず、少数の項目しか述語を満たさない場合、述語を著しく制限するか、効率を損なわなければならない。 我々は、トラバーサルを制約するのではなく、それぞれ異なる述語形式を提供する多くの指標を構築するという、反対のアプローチを提案する。 効率的な構築のために,インデックスサイズ,検索時間,リコールの関係を抽出する3次元解析モデルを考案し,できるだけ多くの有用なインデックスをコレクションに詰め込むために,ワークロード対応アプローチを踏襲する。 クエリ時に、分析モデルは、与えられたリコールで最も高速な検索を提供するものを識別するために、再び使用される。 我々のアプローチは、標準のHNSWグラフの2.15倍のメモリと過去のワークロードの控えめな知識を持ちながら、1%のビルド時間と他のインデックスに対して最大8.06倍のスピードアップを実現しています。

関連論文リスト

• FastGAS: Fast Graph-based Annotation Selection for In-Context Learning [53.17606395275021]
  インコンテキスト学習(ICL)は、大規模言語モデル(LLM)に対して、一連のトレーニングインスタンスをプロンプトとして使用することにより、新しいタスクに対処する権限を与える。 既存の手法では、アノテーションのラベルなし例のサブセットを選択する方法が提案されている。 本稿では,高品質なインスタンスを効率的に識別するグラフベースの選択手法であるFastGASを提案する。
  論文  参考訳（メタデータ） (2024-06-06T04:05:54Z)
• Improved Anonymous Multi-Agent Path Finding Algorithm [3.694001372535405]
  エージェントの集合をグラフに限定する匿名多エージェントパスフィンディング(AMAPF)問題を考える。 我々は,検索空間を探索するアイデアを,個別の検索状態ではなく,一括して考えることによって活用する,特定の検索アルゴリズムを提案する。 その結果、AMAPFソルバは最先端の競合に比べて優れた性能を示し、30秒未満で利用可能なすべてのMAPFインスタンスを解決できる。
  論文  参考訳（メタデータ） (2023-12-17T00:49:30Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQは、マルチタスク学習問題とエンティティペアの分布を回避する、シーングラフ生成の新しい定式化である。 我々は,DETRをベースとしたエンコーダ-デコーダ条件付きクエリを用いて,エンティティラベル空間を大幅に削減する。 実験結果から、TraCQは既存のシングルステージシーングラフ生成法よりも優れており、Visual Genomeデータセットの最先端の2段階メソッドを多く上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-06-09T06:02:01Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  KGQA(Multi-hop Question Answering over Knowledge Graph)は、自然言語の質問で言及されているトピックエンティティから、複数のホップを持つ回答エンティティを見つけることを目的としている。 我々は、モデルアーキテクチャとパラメータ学習の両方において、検索と推論を統合することで、マルチホップKGQAタスクの新しいアプローチであるUniKGQAを提案する。
  論文  参考訳（メタデータ） (2022-12-02T04:08:09Z)
• Integrating connection search in graph queries [6.948362325254044]
  SPARQLやCypherといったグラフクエリ言語に接続ツリーパターン(CTP)を統合する方法を示す。 非常に大きな探索空間に対処するため,我々は効率的な刈り込み手法を提案し,我々のアルゴリズムMOLESPがプルーニングでも完備しているケースの集合を正式に確立する。
  論文  参考訳（メタデータ） (2022-08-09T14:27:57Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
  グラフクエリ拡張(GQE)が提示され、教師付き方法で学習され、クエリの拡張近傍で集約を実行する。 この技術は既知のベンチマークよりも最先端の結果が得られる。
  論文  参考訳（メタデータ） (2021-12-05T19:48:42Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)

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

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