論文の概要: SOLO: Certified-Recall Metric Similarity Search with Scan-Only Sampled Inverted Lists

• arxiv url: http://arxiv.org/abs/2610.02387v2
• Date: Tue, 06 Oct 2026 16:50:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 02:58:29.264906
• Title: SOLO: Certified-Recall Metric Similarity Search with Scan-Only Sampled Inverted Lists
• Title（参考訳）: SOLO: Scan-Only Smpled Inverted Listsを用いた認証リコールメトリック類似検索
• Abstract要約: SOLOは逆ファイルであり、語彙はデータベースのランダムなサンプルである。 各オブジェクトの$k_b$近くのサンプルポイントは一度格納され、ランク付けされる。 演算子のクエリのサンプルを渡すと、一度に$(b, k_s) のすべての値が証明され、何も提供されない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In every fast nearest-neighbor index, recall is measured, never predicted: each operating point is tuned by serving it against ground truth. SOLO is an index whose recall is computed from the index itself, before any query is served. SOLO is an inverted file whose vocabulary is a random sample of the database. Each object's $k_b$ nearest sample points are stored once, ranked; at serve time an object is posted under the first $b \le k_b$ of them, and a query scans the lists of its $k_s$ nearest sample points exhaustively, with the true distance. Recall depends on the product $b \cdot k_s$ (an equal-work law), so the search-side $k_s$ compensates for a small $b$ with no rebuild. There is no beam, vote or pruning bound, so a true neighbor is missed only if it shares no sample point with the query -- a membership event decided by stored integers, not by a search. Recall is therefore a count: one ground-truth pass over a sample of the operator's queries certifies every $(b, k_s)$ at once, with nothing served. The certificate matches served recall to four decimals from $10^6$ to $10^9$ objects, including 768-dimensional text embeddings under inner product with shifted queries. No graph index has an analogous object. The rest is the same rule applied recursively: a list that outgrows a bound is sampled and split like the database, and so is the vocabulary itself, which is what drives resident memory down. Deep-100M is served at recall 0.9977 from 1 GB of enforced resident memory, Deep-1B at 0.9925 from 96 MB. Inserts are one search, deletes are exact, and throughput reaches $1.8\times$ a tuned HNSW at $10^8$. Every number is reported against HNSW, DiskANN, GRAFT, NAPP, misi, SPANN, ScaNN and RaBitQ on the same hardware and ground truth.
• Abstract（参考訳）: 最寄りのすべての高速インデックスでは、リコールは測定され、予測されず、各操作ポイントは、地上の真実に合わせることで調整される。 SOLOは、クエリが提供される前にインデックス自体からリコールされるインデックスである。 SOLOは逆ファイルであり、語彙はデータベースのランダムなサンプルである。 各オブジェクトの$k_b$近くのサンプルポイントは一度格納され、ランク付けされ、サーブ時には、オブジェクトが最初の$b \le k_b$の下にポストされ、クエリは、その$k_s$近くのサンプルポイントのリストを、真の距離で徹底的にスキャンする。 リコールは製品$b \cdot k_s$(等仕事法則)に依存するため、検索側$k_s$はリビルドなしで小さな$b$を補償する。 ビーム、投票、プルーニングバウンダリがないため、真の隣人は、クエリとサンプルポイントを共有していない場合にのみ見逃される -- 検索によってではなく、格納された整数によって決定されるメンバシップイベントである。 1つの接頭辞が演算子のクエリのサンプルを渡すと、一度に$(b, k_s)$が保証され、何も提供されない。 証明書マッチは10^6$から10^9$オブジェクトの4つのデシマルにリコールされる。 グラフインデックスには類似のオブジェクトがない。 残りは再帰的に適用されるのと同じルールである: 境界を超えるリストは、データベースのようにサンプリングされ分割される。 Deep-100Mは1GBのメモリから0.9977で、Deep-1Bは96MBから0.9925でリコールされる。 インサートは1つの検索であり、削除は正確であり、スループットは1.8\times$ a tuned HNSW at 10^8$に達する。 すべての数字は、HNSW, DiskANN, GRAFT, NAPP, misi, SPANN, ScaNN, RaBitQ に対して、同じハードウェアと地上の真実について報告される。

関連論文リスト

• Codebook Agent: Amortized Topology Design for LLM Multi-Agent Systems [67.04448659688579]
  クエリ非依存の16エントリのコードブックを開発し、上位のデコード候補を1回のバッチフォワードパスでランク付けする。 反復検索がなく、テスト時にメッセージパッシングがないため、Codebook Agentは6つのベンチマークでもっとも正確な方法である。
  論文  参考訳（メタデータ） (2026-09-02T08:10:22Z)
• misi: a Metric Inverted Sample Index [0.0]
  mii は一般距離空間上の近似近傍探索のための逆インデックスである。 それぞれのオブジェクトは、$k_b$の最も近いサンプルポイントで表現され、サンプル上のプラグ可能なインナーインデックスによって見つかる。 クエリはidf-weighted shared-neighborの投票によって回答され、続いて$C$の候補の正確な検証が行われる。
  論文  参考訳（メタデータ） (2026-08-27T17:48:22Z)
• Billion-Scale Nearest-Neighbor Search under Fully Homomorphic Encryption on a Single GPU, Balancing Leakage and Cost [1.8050555114021396]
  どのデータベースベクタが私のクエリに最もよく似ているか?」と答えるシステムを構築します。 クエリは完全に同型 En-cryption (FHE) で暗号化される サーバは暗号文でスコア付けを行い、クライアントのみが読める暗号化された結果を返す。
  論文  参考訳（メタデータ） (2026-08-21T14:08:04Z)
• Hierarchical BM25: Lexical Search at Billion-Document Scale [0.9991706230252708]
  BM25指数は10億以上の文書が約400GBを占めている。 したがって、このスケールでの正確なトップk語彙検索は、対話的なレイテンシー予算の中では現実的ではない。 ウォームドキャッシュは1秒あたり32クエリを持続するが、フラットインデックスは3以下である。
  論文  参考訳（メタデータ） (2026-07-31T19:18:37Z)
• A Survey of Spatial Memory Representations for Efficient Robot Navigation [4.560386676154887]
  52のシステムにまたがる88の参照の空間記憶効率の問題を調査した。 M_textpeak / M_textmap$は、ピーク時メモリ(操作中に消費される全RAMまたはGPUメモリ)と保存されたマップサイズとの比率である。
  論文  参考訳（メタデータ） (2026-04-13T02:12:17Z)
• HISA: Efficient Hierarchical Indexing for Fine-Grained Sparse Attention [62.79085204939384]
  HISA (Hierarchical Indexed Sparse Attention) は、平らなトークンスキャンから2段階の階層的な手順に検索パスを書き換える。 カーネルレベルのベンチマークでは、HISAは64Kコンテキストでの高速化を実現している。
  論文  参考訳（メタデータ） (2026-03-30T13:59:51Z)
• Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Index [110.90283601829724]
  ペタバイトレベルのテキストコーパスを検索可能にするシステムであるinfini-gram miniを提案する。 FMインデックスデータ構造に基づいて,本システムはコーパスの44%の大きさのインデックスを生成する。 ベンチマーク汚染の大規模解析において重要なユースケースが1つある。
  論文  参考訳（メタデータ） (2025-06-13T21:13:57Z)
• Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search [57.18075258042082]
  このコンペティションは、ANNSアルゴリズムをハードウェアコスト、精度、性能で数十億ドル規模で比較する。 このコンペティションのために新たに4つの、60億の多様なデータセットをまとめました。
  論文  参考訳（メタデータ） (2022-05-08T02:41:54Z)
• SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search [39.361122198195076]
  本稿では,SPANNというメモリディスクハイブリッドインデックスと検索システムを提案する。 ポストリストのセントロイドポイントをメモリに、大きなポストリストをディスクに格納する。 リコール@1とリコール@10はわずか1ミリ秒で、メモリは32GBだ。
  論文  参考訳（メタデータ） (2021-11-05T06:28:15Z)

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

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