論文の概要: OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries

• arxiv url: http://arxiv.org/abs/2211.12850v1
• Date: Sat, 22 Oct 2022 21:22:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-27 13:38:42.247185
• Title: OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries
• Title（参考訳）: OOD-DiskANN: アウトオブディストリビューションクエリのための効率的でスケーラブルなグラフANNS
• Authors: Shikhar Jaiswal, Ravishankar Krishnaswamy, Ankit Garg, Harsha Vardhan Simhadri, Sheshansh Agrawal
• Abstract要約: Approximate Nearest Neighbor Search (ANNS)の最先端アルゴリズムは、インデックスデータ分布にオーバーフィットすることで、データに依存したインデックスを構築する。 OOD-DiskANNはOODクエリのスペーリングサンプル(インデックスセットサイズの1%)を使用し、同じメモリフットプリントのSoTAアルゴリズムに対して、平均クエリレイテンシを最大40%改善する。
• 参考スコア（独自算出の注目度）: 8.950168559003993
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: State-of-the-art algorithms for Approximate Nearest Neighbor Search (ANNS) such as DiskANN, FAISS-IVF, and HNSW build data dependent indices that offer substantially better accuracy and search efficiency over data-agnostic indices by overfitting to the index data distribution. When the query data is drawn from a different distribution - e.g., when index represents image embeddings and query represents textual embeddings - such algorithms lose much of this performance advantage. On a variety of datasets, for a fixed recall target, latency is worse by an order of magnitude or more for Out-Of-Distribution (OOD) queries as compared to In-Distribution (ID) queries. The question we address in this work is whether ANNS algorithms can be made efficient for OOD queries if the index construction is given access to a small sample set of these queries. We answer positively by presenting OOD-DiskANN, which uses a sparing sample (1% of index set size) of OOD queries, and provides up to 40% improvement in mean query latency over SoTA algorithms of a similar memory footprint. OOD-DiskANN is scalable and has the efficiency of graph-based ANNS indices. Some of our contributions can improve query efficiency for ID queries as well.
• Abstract（参考訳）: DiskANN、FAISS-IVF、HNSWなどの近似近傍探索(ANNS)のための最先端アルゴリズムは、インデックスデータ分布に過度に適合することにより、データ非依存指標よりも精度と探索効率を大幅に向上させるデータ依存指標を構築する。 例えば、インデックスがイメージの埋め込みを表し、クエリがテキストの埋め込みを表す場合、クエリデータが別のディストリビューションから引き出されると、そのようなアルゴリズムはパフォーマンス上の利点をほとんど失う。 様々なデータセットにおいて、固定されたリコールターゲットでは、In-Distribution (ID)クエリと比較して、Out-Of-Distribution (OOD)クエリのレイテンシは桁違いに悪化する。 この研究で私たちが直面している疑問は、インデックス構築がこれらのクエリの小さなサンプルセットにアクセスできれば、ANNSアルゴリズムをOODクエリに効率的に適用できるかどうかである。 OOD-DiskANNはOODクエリのスパーリングサンプル(インデックスセットサイズの1%)を使用しており、同じメモリフットプリントのSoTAアルゴリズムよりも40%のクエリレイテンシが改善されている。 OOD-DiskANNはスケーラブルで、グラフベースのANNSインデックスの効率性がある。 コントリビューションのいくつかは、IDクエリのクエリ効率を改善することができます。

関連論文リスト

• Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
  本稿では,オープンソースのLucene検索ライブラリを用いたBEIRデータセットの実験結果について述べる。 本研究は,高密度かつ疎密なレトリバーの設計空間を理解するための,今日の検索実践者へのガイダンスを提供する。
  論文  参考訳（メタデータ） (2024-09-10T12:46:23Z)
• 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)
• Semi-Parametric Retrieval via Binary Token Index [71.78109794895065]
  Semi-parametric Vocabulary Disentangled Retrieval (SVDR) は、新しい半パラメトリック検索フレームワークである。 既存のニューラル検索手法に似た、高い有効性のための埋め込みベースのインデックスと、従来の用語ベースの検索に似た、迅速かつ費用対効果の高いセットアップを可能にするバイナリトークンインデックスの2つのタイプをサポートする。 埋め込みベースインデックスを使用する場合の高密度検索器DPRよりも3%高いトップ1検索精度と、バイナリトークンインデックスを使用する場合のBM25よりも9%高いトップ1検索精度を実現する。
  論文  参考訳（メタデータ） (2024-05-03T08:34:13Z)
• Constructing Tree-based Index for Efficient and Effective Dense Retrieval [26.706985694158384]
  JTRは、TReeベースのインデックスとクエリエンコーディングの合同最適化の略である。 我々は、木に基づくインデックスとクエリエンコーダをエンドツーエンドにトレーニングするために、新しい統合されたコントラスト学習損失を設計する。 実験結果から,JTRは高いシステム効率を維持しつつ,検索性能が向上することが示された。
  論文  参考訳（メタデータ） (2023-04-24T09:25:39Z)
• WISK: A Workload-aware Learned Index for Spatial Keyword Queries [46.96314606580924]
  本稿では,空間的キーワードクエリの学習指標であるWISKを提案する。 We show that WISK achieve up to 8x speedup in querying time with comparable storage overhead。
  論文  参考訳（メタデータ） (2023-02-28T03:45:25Z)
• A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
  LIMSは、学習したインデックスを構築するために、データクラスタリングとピボットベースのデータ変換技術を使用することが提案されている。 機械学習モデルはディスク上の各データレコードの位置を近似するために開発された。 実世界のデータセットと合成データセットに関する大規模な実験は、従来の指標と比較してLIMSの優位性を示している。
  論文  参考訳（メタデータ） (2022-04-21T11:24:55Z)
• Compactness Score: A Fast Filter Method for Unsupervised Feature Selection [66.84571085643928]
  本稿では,CSUFS (Compactness Score) と呼ばれる高速な教師なし特徴選択手法を提案する。 提案アルゴリズムは既存のアルゴリズムよりも正確で効率的である。
  論文  参考訳（メタデータ） (2022-01-31T13:01:37Z)
• A Pluggable Learned Index Method via Sampling and Gap Insertion [48.900186573181735]
  データベースインデックスは、データ検索を促進し、現実世界のシステムにおける幅広いアプリケーションに役立つ。 近年,隠れて有用なデータ分布を学習するために,learning indexという新しいインデックスが提案されている。 学習指標の学習効率と学習効率を高めるための2つの一般的なテクニックとプラグイン可能なテクニックを研究します。
  論文  参考訳（メタデータ） (2021-01-04T07:17:23Z)
• 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)
• COAX: Correlation-Aware Indexing on Multidimensional Data with Soft Functional Dependencies [3.670422696827525]
  データセットの属性間の相関関係を学習する多次元データのための学習指標であるCOAXを提案する。 実験により,データ中の関連属性を予測することにより,クエリ実行時間を短縮し,インデックスのメモリオーバーヘッドを低減することができることがわかった。
  論文  参考訳（メタデータ） (2020-06-29T21:22:15Z)

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

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