論文の概要: CertEx: Exact Visual Retrieval at Scale by Certified Exclusion

• arxiv url: http://arxiv.org/abs/2610.21325v1
• Date: Thu, 15 Oct 2026 06:16:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 19:13:16.213241
• Title: CertEx: Exact Visual Retrieval at Scale by Certified Exclusion
• Title（参考訳）: CertEx: Certified Exclusionによる大規模ビジュアル検索
• Abstract要約: certexは7.1$times$から18.0$times$のクエリに対して正確である。 Certexは各ベクトルの下界投影を半精度で保存し、ラウンドリング証明書を同じテンソルコアドット積に折り畳む。 1億のベクトルを持つ16のデータセットでは、Certexは1つのH100上で最も高速なcuVS検索のスループットに対して7.1$times$から18.0$times$のクエリに対して正確である。
• 参考スコア（独自算出の注目度）: 0.9179857807576733
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Exact $k$-nearest-neighbor (kNN) search over image descriptors and embeddings underlies visual retrieval, near-duplicate detection, the evaluation of learned representations, and increasingly the memory of LLM agents. However, exhaustive search computes every distance at full precision, whereas approximate indexes return recall below one. We observe that exact search only needs a proof that each excluded vector cannot be a neighbor. Because such a proof only has to be conservative, it can be checked in low precision, much as the retina examines the whole scene at low resolution. We call this principle certified exclusion and realize it in an exact kNN method for GPUs, which we call \certex. Specifically, \certex\ stores a lower-bounding projection of each vector in half precision and folds a rounding certificate into the same tensor-core dot product, so that only the few vectors that the test keeps need exact distances. We prove that \certex\ returns the exact kNN of every query. On sixteen datasets with up to 100M vectors, \certex\ is exact for every query at 7.1$\times$ to 18.0$\times$ the throughput of the fastest cuVS search on one H100 and outperforms quantized and graph indexes whenever every query must be exact.
• Abstract（参考訳）: Exact $k$-nearest-neighbor (kNN) search over image descriptor and embeddingsは、視覚的検索、ほぼ重複検出、学習された表現の評価、LLMエージェントの記憶の増大をもたらす。 しかし、徹底的な探索は全精度で全ての距離を計算し、一方近似インデックスは1以下のリコールを返す。 正確な探索は、各排除ベクトルが隣人にならないという証明しか必要としない。 このような証明は保守的である必要があるため、網膜が低解像度でシーン全体を検査するのと同様に、低い精度で検査することができる。 我々は、この原理を認証排除と呼び、GPUの正確なkNNメソッドで実現し、それを \certex と呼ぶ。 具体的には、 \certex\ は各ベクトルの下界射影を半精度で保存し、丸め証明書を同じテンソルコアのドット積に折り畳み、テストが保持する少数のベクトルだけが正確な距離を必要とする。 私たちは \certex\ が全てのクエリの正確な kNN を返すことを証明します。 1億のベクトルを持つ16のデータセットにおいて、 \certex\は7.1$\times$から18.0$\times$のクエリに対して正確である。

関連論文リスト

• Token-Budgeted Candidate Retrieval for 3D Scene-Grounded VLMs: Category Names vs. Pairwise Geometry [0.0]
  ScanNet屋内参照ベンチマークでは、クエリとオブジェクトカテゴリ名とのマッチングは、報告されたK毎にペアワイズ幾何スコアよりも優れている。 我々は,各オブジェクトのカテゴリ名とqと一致する2つの小さなエンコーダと,決定論的対幾何スコアであるQCRR(Query-Conditioned Relation Retrieval)を用いて,軸整列ボックス,トークン比メトリック,トレーニング不要ベースライン,およびトークン予算による候補検索を評価する。
  論文  参考訳（メタデータ） (2026-10-09T18:17:02Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• Scaling Neural Network Verification with Tensor Parallelism and Fully Sharded Data Parallelism [0.0]
  形式的ニューラルネットワーク検証は、実際にはGPUメモリによって境界付けられている。 大規模なモデルトレーニングのために開発された2つのテクニックをauto_LiRPA / $,$-CROWN 検証フレームワークに適用する。 フルシャードデータ並列(FSDP)シャードは、層ごとのAllGatherで重量行列のみをシャードし、単一GPUベースラインとビット単位で同一のバウンドを生成する。
  論文  参考訳（メタデータ） (2026-06-08T11:56:29Z)
• δ-EMG: A Monotonic Graph Index for Approximate Nearest Neighbor Search [33.62724124122037]
  本稿では,クエリ時における近似精度を制御する誤り境界付きANN探索アルゴリズムを提案する。 0.99のリコール条件下では、SIFT1Mデータセット上で19,000QPSを達成し、他の手法よりも40%以上性能が向上する。
  論文  参考訳（メタデータ） (2025-11-21T03:20:54Z)
• Fast Exact Retrieval for Nearest-neighbor Lookup (FERN) [0.0]
  厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 近距離近傍探索(FERN)のための対数的高速エクササイズ検索のための新しいアルゴリズムを提案する。 このアルゴリズムは1000万ドルの$d=128$に対して100%リコールした$O(dlog N)$ルックアップを達成する。
  論文  参考訳（メタデータ） (2024-05-07T15:57:39Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximation [53.95297550117153]
  本稿では,大規模な視覚データテンソルの処理を行うエンドツーエンドのトレーニング可能なフレームワークを提案する。 提案手法は大規模多次元グリッドデータや,大規模受容領域上のコンテキストを必要とするタスクに特に有用である。
  論文  参考訳（メタデータ） (2021-05-29T08:39:57Z)
• Sparse R-CNN: End-to-End Object Detection with Learnable Proposals [77.9701193170127]
  Sparse R-CNNは、画像中の物体検出のための純粋にスパースな方法である。 最終的な予測は、最大でない処理後抑制なしで直接出力される。 われわれの研究が、物体検知器に先立って密集した慣例を再考することを願っている。
  論文  参考訳（メタデータ） (2020-11-25T00:01:28Z)

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

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