論文の概要: Range Retrieval with Graph-Based Indices
- arxiv url: http://arxiv.org/abs/2502.13245v2
- Date: Fri, 21 Feb 2025 15:20:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-24 12:49:58.645449
- Title: Range Retrieval with Graph-Based Indices
- Title（参考訳）: グラフに基づく指標を用いた範囲検索
- Authors: Magdalen Dobson Manohar, Taekseung Kim, Guy E. Blelloch,
- Abstract要約: 高次元ベクトル空間における近接点の検索は,情報検索における重要なステップである。
本稿では,グラフに基づくベクトル指標を用いた範囲探索アルゴリズムを提案する。
単純なベースラインアプローチよりも,クエリスループットが最大100倍,平均で5～10倍,パフォーマンスが最大1億データポイントまで向上しています。
- 参考スコア（独自算出の注目度）: 0.294944680995069
- License:
- Abstract: Retrieving points based on proximity in a high-dimensional vector space is a crucial step in information retrieval applications. The approximate nearest neighbor search (ANNS) problem, which identifies the $k$ nearest neighbors for a query (approximately, since exactly is hard), has been extensively studied in recent years. However, comparatively little attention has been paid to the related problem of finding all points within a given distance of a query, the range retrieval problem, despite its applications in areas such as duplicate detection, plagiarism checking, and facial recognition. In this paper, we present a set of algorithms for range retrieval on graph-based vector indices, which are known to achieve excellent performance on ANNS queries. Since a range query may have anywhere from no matching results to thousands of matching results in the database, we introduce a set of range retrieval algorithms based on modifications of the standard graph search that adapt to terminate quickly on queries in the former group, and to put more resources into finding results for the latter group. Due to the lack of existing benchmarks for range retrieval, we also undertake a comprehensive study of range characteristics of existing embedding datasets, and select a suitable range retrieval radius for eight existing datasets with up to 100 million points in addition to the one existing benchmark. We test our algorithms on these datasets, and find up to 100x improvement in query throughput over a naive baseline approach, with 5-10x improvement on average, and strong performance up to 100 million data points.
- Abstract（参考訳）: 高次元ベクトル空間における近接点の検索は,情報検索における重要なステップである。
クェリに最も近い近接探索(ANNS)問題は、クエリに$k$近い隣人(正確には難しい)を識別する問題であり、近年広く研究されている。
しかし、重複検出、盗作検査、顔認識などの分野に応用されているにもかかわらず、クエリの所定の距離内にある全ての点を見つけるという関連する問題や範囲検索の問題には、比較的注意が払われていない。
本稿では,ANNSクエリにおいて優れた性能を示すことが知られているグラフベースベクトルインデックスのレンジ検索アルゴリズムを提案する。
レンジクエリはデータベース内の何千というマッチング結果から数千のマッチング結果まで,どこにでも存在し得るので,従来のグループ内のクエリで素早く終了するように適応する標準グラフ検索の修正に基づいて,レンジ検索アルゴリズムのセットを導入し,後者のグループの検索結果により多くのリソースを投入する。
既存の範囲検索のベンチマークが不足しているため、既存の埋め込みデータセットのレンジ特性を網羅的に調査し、既存の8つのデータセットに対して、最大1億ポイントのレンジ検索半径を選択するとともに、既存の1つのベンチマークの他に、適切な範囲検索半径を選択する。
これらのデータセット上でアルゴリズムをテストし、単純なベースラインアプローチによるクエリスループットを最大100倍改善し、平均で5～10倍の改善、最大1億のデータポイントのパフォーマンス向上を実現しています。
関連論文リスト
- Learning Cluster Representatives for Approximate Nearest Neighbor Search [0.0]
この論文はクラスタリングに基づく近似近傍探索の包括的説明を提供する。
また、新しい最先端の手法のあらゆる側面を紹介し、掘り下げます。
この直感の発達と,それを内積探索の最大化に適用することにより,単純な線形関数を用いた学習クラスタ代表がクラスタリングに基づく近接探索の精度を大幅に向上させることを示した。
論文 参考訳（メタデータ） (2024-12-08T12:31:32Z) - iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search [24.85572470526277]
周辺地域を探索するRFANN(Range-filtering Near Near Near Near neighbor)は、学術や産業で注目を集めている。
最近の研究では、可能な全てのクエリ範囲に対して、$O(n2)$専用のグラフベースのインデックスを構築することを提案する。
要素グラフと呼ばれるグラフベースのインデックスを適度な範囲で作成する。
論文 参考訳（メタデータ） (2024-09-04T09:41:52Z) - BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrieval [54.54576644403115]
多くの複雑な実世界のクエリは、関連する文書を特定するために詳細な推論を必要とする。
BRIGHTは、関係する文書を検索するために、集中的推論を必要とする最初のテキスト検索ベンチマークである。
私たちのデータセットは、経済学、心理学、数学、コーディングなど、さまざまな領域にまたがる1,384の現実世界のクエリで構成されています。
論文 参考訳（メタデータ） (2024-07-16T17:58:27Z) - 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) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - 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) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。
代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。
データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文 参考訳（メタデータ） (2021-12-06T20:34:55Z) - Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
グラフクエリ拡張(GQE)が提示され、教師付き方法で学習され、クエリの拡張近傍で集約を実行する。
この技術は既知のベンチマークよりも最先端の結果が得られる。
論文 参考訳（メタデータ） (2021-12-05T19:48:42Z) - Cross-Domain Generalization Through Memorization: A Study of Nearest
Neighbors in Neural Duplicate Question Detection [72.01292864036087]
重複質問検出(DQD)は,コミュニティの効率向上と自動質問応答システムの実現に重要である。
我々は、DQDのクロスドメイン一般化のために、ニューラル表現を活用し、近接する隣人を研究する。
StackExchange、Spring、Quoraの各データセットの異なるクロスドメインシナリオにおいて、このメソッドの堅牢なパフォーマンスを観察します。
論文 参考訳（メタデータ） (2020-11-22T19:19:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。