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

• arxiv url: http://arxiv.org/abs/2610.02387v1
• Date: Thu, 01 Oct 2026 19:09:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 19:20:54.748468
• Title: SOLO: Certified-Recall Metric Similarity Search with Scan-Only Sampled Inverted Lists
• Title（参考訳）: SOLO: Scan-Only Smpled Inverted Listsを用いた認証リコールメトリック類似検索
• Abstract要約: SOLO は一般距離空間における近似近傍探索の指標である。 クエリはデータベースのランダムなサンプルの$k_s$最寄りのポイントにルーティングされる。 タッチされた投稿リストにあるすべてのオブジェクトは、真の距離で評価される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present SOLO, an index for approximate nearest-neighbor search in general metric spaces whose serving path contains no ranking heuristic of any kind: a query is routed to the $k_s$ nearest points of a random sample of the database, and every object in the touched posting lists is evaluated with the true distance. Because nothing must outrank anything, recall equals a coverage probability computable from the stored index: one ground-truth pass over a query sample certifies every operating point at once, without serving any of them -- a recall certificate, and for a navigable graph no analogous object exists at any price. The whole index is one recursive rule -- sample the collection, post each object to its $b$ nearest sample points, split any list that outgrows a bound, always scan the leaves -- and its operating surface obeys an equal-work law, recall $\approx f(b \cdot k_s)$, whose level is a one-scalar signature of the dataset. The same scan-only structure gives a serving floor no graph architecture reaches once the router is itself indexed by the same rule: Deep-100M served at recall 0.9977 from 1 GB of resident memory (enforced cap, 10.7 bytes per object) and at 0.9964 from 256 MB, Deep-1B at recall 0.9925 from 512 MB (and from 96 MB at depth 3), inserts that are one search, and deletes that are exact. Throughput is competitive where the hardware allows it -- up to $1.8\times$ a tuned HNSW at $10^8$ on a two-socket 32-core server, with operating points to the right of where that graph saturates -- and the tables report it against HNSW, DiskANN, GRAFT, NAPP, misi, and SPANN's assignment rule on the same hardware and ground truth.
• Abstract（参考訳）: 本稿では,データベースのランダムなサンプルの$k_s$に近い点にクエリをルーティングし,タッチされたポストリストのすべてのオブジェクトを真の距離で評価する。 何かをオーバーランする必要はないため、リコールは、格納されたインデックスから計算可能なカバレッジ確率に等しい。 1つのグランドトルースは、クエリのサンプルが一度にすべてのオペレーションポイントを認証する -- リコール証明書、ナビゲート可能なグラフには、どんな価格でも類似したオブジェクトは存在しない。インデックス全体は、1つの再帰的なルールである -- コレクションをサンプリングし、各オブジェクトをその$b$のサンプルポイントにポストし、バウンドを出し、常に葉をスキャンするリストを分割する。そして、その操作面は、等しい作業法に従って、$\approx f(b \cdot k_s)$をリコールする。 ディープ100Mは1GBの常備メモリから0.9977、256MBから0.9964、256MBからDeep-1B、512MBから0.9925、深度3から96MBから)、1回の検索で挿入され、正確に削除される。 スループットはハードウェアが許容する -- 最大1.8\times$ 10^8$のHNSWを2ソケットの32コアサーバで処理し、そのグラフが飽和した場所の右側にオペレーションポイントを配置 -- で、テーブルはHNSW、DiskANN、GRAFT、NAPP、mimi、SPANNの割り当てルールを同じハードウェアと地上の真理に対してレポートする。

関連論文リスト

• 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)

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

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