論文の概要: iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search
- arxiv url: http://arxiv.org/abs/2409.02571v1
- Date: Wed, 04 Sep 2024 09:41:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-10 16:25:07.314690
- Title: iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search
- Title（参考訳）: iRangeGraph: 近距離探索のためのレンジ指定グラフの改善
- Authors: Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, Christian S. Jensen,
- Abstract要約: 周辺地域を探索するRFANN(Range-filtering Near Near Near Near neighbor)は、学術や産業で注目を集めている。
最近の研究では、可能な全てのクエリ範囲に対して、$O(n2)$専用のグラフベースのインデックスを構築することを提案する。
要素グラフと呼ばれるグラフベースのインデックスを適度な範囲で作成する。
- 参考スコア（独自算出の注目度）: 24.85572470526277
- License:
- Abstract: Range-filtering approximate nearest neighbor (RFANN) search is attracting increasing attention in academia and industry. Given a set of data objects, each being a pair of a high-dimensional vector and a numeric value, an RFANN query with a vector and a numeric range as parameters returns the data object whose numeric value is in the query range and whose vector is nearest to the query vector. To process this query, a recent study proposes to build $O(n^2)$ dedicated graph-based indexes for all possible query ranges to enable efficient processing on a database of $n$ objects. As storing all these indexes is prohibitively expensive, the study constructs compressed indexes instead, which reduces the memory consumption considerably. However, this incurs suboptimal performance because the compression is lossy. In this study, instead of materializing a compressed index for every possible query range in preparation for querying, we materialize graph-based indexes, called elemental graphs, for a moderate number of ranges. We then provide an effective and efficient algorithm that during querying can construct an index for any query range using the elemental graphs. We prove that the time needed to construct such an index is low. We also cover an experimental study on real-world datasets that provides evidence that the materialized elemental graphs only consume moderate space and that the proposed method is capable of superior and stable query performance across different query workloads.
- Abstract（参考訳）: 周辺地域を探索するRFANN(Range-filtering Near Near Near Near neighbor)は、学術や産業で注目を集めている。
高次元ベクトルと数値値のペアであるデータオブジェクトのセットが与えられたとき、パラメータとしてベクトルと数値範囲のRFANNクエリは、クエリ範囲に数値値があり、クエリベクトルに最も近いデータオブジェクトを返します。
このクエリを処理するために、最近の研究では、$O(n^2)$専用グラフベースのインデックスを全てのクエリ範囲に対して構築し、$n$オブジェクトのデータベース上で効率的な処理を可能にすることを提案している。
これらの指標の保存は違法に高価であるため、代わりに圧縮インデックスを構築し、メモリ消費を大幅に削減する。
しかし、圧縮が損なわれるため、これは準最適性能を損なう。
本研究では,クエリのためのクエリ範囲毎に圧縮インデックスを作成する代わりに,要素グラフと呼ばれるグラフベースのインデックスを適度な範囲で作成する。
次に、クエリ中に要素グラフを用いて任意のクエリ範囲のインデックスを構築することができる、効率的かつ効率的なアルゴリズムを提案する。
このような指標を構築するのに必要な時間は低いことを証明します。
また、実世界のデータセットに関する実験研究を行い、物質化された要素グラフが適度な空間しか消費しないことを示すとともに、提案手法は、異なるクエリワークロードに対して、優れた、安定したクエリ性能を実現することができることを示す。
関連論文リスト
- Vector search with small radiuses [10.880913075221361]
本稿では,ベクトル検索結果に応じて難しい決定を下す必要がある場合に着目する。
本研究では,クエリー・ツー・ベクター距離に基づいて,範囲探索結果の値を厳密にモデル化できることを示す。
これにより、範囲探索の指標 RSM が得られ、これは原則的であり、エンドツーエンドの評価を行なわずに計算が容易である。
論文 参考訳（メタデータ） (2024-03-16T00:34:25Z) - Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。
本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。
本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
論文 参考訳（メタデータ） (2023-11-05T06:12:03Z) - 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) - 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) - 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) - A Practical Index Structure Supporting Fr\'echet Proximity Queries Among
Trajectories [1.9335262420787858]
我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。
計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。
本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
論文 参考訳（メタデータ） (2020-05-28T04:12:43Z) - Progressively Pretrained Dense Corpus Index for Open-Domain Question
Answering [87.32442219333046]
本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。
本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
論文 参考訳（メタデータ） (2020-04-30T18:09:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。