論文の概要: SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2111.08566v1
• Date: Fri, 5 Nov 2021 06:28:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-21 16:38:49.511434
• Title: SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search
• Title（参考訳）: SPANN: 高効率な数十億ドル規模の近似的近隣検索
• Authors: Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, Jingdong Wang
• Abstract要約: 本稿では,SPANNというメモリディスクハイブリッドインデックスと検索システムを提案する。 ポストリストのセントロイドポイントをメモリに、大きなポストリストをディスクに格納する。 リコール@1とリコール@10はわずか1ミリ秒で、メモリは32GBだ。
• 参考スコア（独自算出の注目度）: 39.361122198195076
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The in-memory algorithms for approximate nearest neighbor search (ANNS) have achieved great success for fast high-recall search, but are extremely expensive when handling very large scale database. Thus, there is an increasing request for the hybrid ANNS solutions with small memory and inexpensive solid-state drive (SSD). In this paper, we present a simple but efficient memory-disk hybrid indexing and search system, named SPANN, that follows the inverted index methodology. It stores the centroid points of the posting lists in the memory and the large posting lists in the disk. We guarantee both disk-access efficiency (low latency) and high recall by effectively reducing the disk-access number and retrieving high-quality posting lists. In the index-building stage, we adopt a hierarchical balanced clustering algorithm to balance the length of posting lists and augment the posting list by adding the points in the closure of the corresponding clusters. In the search stage, we use a query-aware scheme to dynamically prune the access of unnecessary posting lists. Experiment results demonstrate that SPANN is 2$\times$ faster than the state-of-the-art ANNS solution DiskANN to reach the same recall quality $90\%$ with same memory cost in three billion-scale datasets. It can reach $90\%$ recall@1 and recall@10 in just around one millisecond with only 32GB memory cost. Code is available at: {\footnotesize\color{blue}{\url{https://github.com/microsoft/SPTAG}}}.
• Abstract（参考訳）: 近距離探索(anns)のためのインメモリアルゴリズムは高速高リコール検索で大きな成功を収めているが、大規模データベースを扱う場合は非常に高価である。 そのため、小型メモリと安価なソリッドステートドライブ(SSD)を備えたハイブリッドANNSソリューションの要求が高まっている。 本稿では,逆インデックス手法に準拠した簡易かつ効率的なメモリ・ディスクハイブリッドインデックス・検索システムspannを提案する。 ポストリストのセントロイドポイントをメモリに、大きなポストリストをディスクに格納する。 ディスクアクセス数を効果的に削減し、高品質なポストリストを取得することにより、ディスクアクセス効率(低レイテンシ)と高リコールの両方を保証します。 インデックス構築段階では,ポストリストの長さのバランスをとるために階層的均衡クラスタリングアルゴリズムを採用し,対応するクラスタのクロージャにポイントを追加することでポストリストを拡大する。 検索段階では、クエリ対応スキームを使用して不要な投稿リストへのアクセスを動的にプルークする。 実験の結果、SPANNは最先端のANNSソリューションであるDiskANNよりも2$\times$速く、同じリコール品質に到達し、30億スケールのデータセットで同じメモリコストで90$%であることがわかった。 約1ミリ秒で$90\%$ recall@1 と recall@10 に到達でき、メモリは32gbに抑えられる。 コードは次の通りである。 {\footnotesize\color{blue}{\url{https://github.com/microsoft/SPTAG}}}。

関連論文リスト

• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval [1.099532646524593]
  DiskANNは、RAMとストレージの両方を使用して、大規模データセットのリコール速度バランスを良好に実現している。 製品量子化(PQ)による圧縮ベクターのロードによるメモリ使用量の削減を主張する一方で、そのメモリ使用量はデータセットの規模に比例して増加する。 本稿では、圧縮されたベクトルをストレージにオフロードするAiSAQ(All-in-Storage ANNS with Product Quantization)を提案する。
  論文  参考訳（メタデータ） (2024-04-09T04:20:27Z)
• Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations [20.944914202453962]
  グラフに基づく近似近傍探索アルゴリズムの最悪の性能について検討する。 DiskANNの場合、その"スロープリプロセッシング"バージョンは、ほぼ近隣の検索クエリを確実にサポートしている。 本稿では,「理にかなった」精度を達成するのに要する経験的なクエリ時間が,インスタンスサイズにおいて線形であるインスタンス群を提案する。
  論文  参考訳（メタデータ） (2023-10-29T19:25:48Z)
• Injecting Domain Adaptation with Learning-to-hash for Effective and Efficient Zero-shot Dense Retrieval [49.98615945702959]
  我々は,TAS-B高密度検索器の下流ゼロショット検索精度を向上させるためのLTHおよびベクトル圧縮技術を評価する。 以上の結果から, 従来の研究とは異なり, LTH法はゼロショットTAS-B高密度レトリバーを平均14%のnDCG@10で過小評価できることがわかった。
  論文  参考訳（メタデータ） (2022-05-23T17:53:44Z)
• Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search [57.18075258042082]
  このコンペティションは、ANNSアルゴリズムをハードウェアコスト、精度、性能で数十億ドル規模で比較する。 このコンペティションのために新たに4つの、60億の多様なデータセットをまとめました。
  論文  参考訳（メタデータ） (2022-05-08T02:41:54Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。 クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。 我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
  論文  参考訳（メタデータ） (2021-03-17T23:13:25Z)
• ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and Gradient Accumulation [106.04777600352743]
  微分可能なアーキテクチャサーチ(DARTS)は、スーパーネット全体がメモリに格納されているため、メモリコストが大幅に低下する。 シングルパスのDARTSが登場し、各ステップでシングルパスのサブモデルのみを選択する。 メモリフレンドリーだが、計算コストも低い。 RObustifying Memory-Efficient NAS (ROME) と呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-23T06:34:07Z)
• Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation [40.75034970144169]
  SLASHはテラバイト規模のデータセットの類似性を近似的に検索する分散システムである。 SLASHはこの2.3テラバイトのデータを1時間以内に20ノードにインデックスし、クエリ時間をミリ秒単位で表示する。
  論文  参考訳（メタデータ） (2020-08-05T18:15:36Z)
• DA-NAS: Data Adapted Pruning for Efficient Neural Architecture Search [76.9225014200746]
  ニューラルネットワーク探索(NAS)における効率的な探索は中核的な問題である 本稿では,大規模ターゲットタスクのアーキテクチャを直接検索できるDA-NASを提案する。 従来の手法より2倍速く、精度は現在最先端であり、小さなFLOPの制約下で76.2%である。
  論文  参考訳（メタデータ） (2020-03-27T17:55:21Z)

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

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