Fugu-MT 論文翻訳(概要): misi: a Metric Inverted Sample Index

論文の概要: misi: a Metric Inverted Sample Index

arxiv url: http://arxiv.org/abs/2608.27422v1
Date: Thu, 27 Aug 2026 17:48:22 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-28 16:30:58.516931
Title: misi: a Metric Inverted Sample Index
Title（参考訳）: mii:Metric Inverted Sample Index
Abstract要約: mii は一般距離空間上の近似近傍探索のための逆インデックスである。それぞれのオブジェクトは、$k_b$の最も近いサンプルポイントで表現され、サンプル上のプラグ可能なインナーインデックスによって見つかる。クエリはidf-weighted shared-neighborの投票によって回答され、続いて$C$の候補の正確な検証が行われる。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present misi, an inverted index for approximate nearest-neighbor search over general metric spaces whose vocabulary is a random sample of the database, of size proportional to $n$. Each object is represented by its $k_b$ nearest sample points, found by a pluggable inner index over the sample; queries are answered by an idf-weighted shared-neighbor vote followed by exact verification of $C$ candidates. The construction generalizes the NAPP index from a constant number of pivots to a linear-size vocabulary, which keeps posting lists at constant expected length $ρ= k_b/α$ as $n$ grows and turns the index into a combinator: any high-recall index on $αn$ points yields an index on $n$ points, for any metric. A probabilistic model gives a recall guarantee -- $k_b$ logarithmic in $n$ over the overlap gap suffices, with a verification budget the index itself estimates -- and a matching limit: the vote cannot resolve overlap differences below order $1/\sqrt{k_b}$. The design's strengths are structural: construction is $n$ independent searches -- embarrassingly parallel, deterministic, $5{,}250$ s for $10^8$ vectors on 64 cores, $3.7\times$ faster than a matched-recall graph build -- it streams under an enforced 3 GiB cap, and the portable artifact serves $10^8$ vectors from NVMe within an enforced 8 GB budget, below the working floor of the SSD-graph baseline. Its cost is query-time work: saturated graph baselines answer $6$-$16\times$ faster in RAM, and the verification budget for 0.99 recall grows as $n^{0.30}$. All results carry seeds, saturation sweeps and full configurations, are generated from run manifests, and include measured negative results. The intended applications weight construction cost, determinism, memory footprint, or black-box metrics over peak throughput: frequently rebuilt corpora, batch similarity workloads, constrained-memory serving.
Abstract（参考訳）: 語彙がデータベースのランダムなサンプルである一般距離空間上の近似近傍探索のための逆インデックスであるmisiを、$n$に比例して提示する。クエリはidf-weighted shared-neighborの投票で回答され、その後$C$の候補の正確な検証が行われる。この構成は、NAPPインデックスを一定数のピボットから線形サイズのボキャブラリに一般化し、$ρ= k_b/α$ as $n$が成長して、インデックスをコンビネータに変える:$αn$ポイント上の任意のハイリコールインデックスは、任意の計量に対して$n$ポイント上のインデックスを生成する。確率的モデルは --$k_b$ logarithmic in $n$というリコール保証を与え、オーバーラップギャップが十分であり、その検証予算はインデックス自体が見積もっている -- そして、一致した制限を与える: 投票はオーバーラップの差を1/\sqrt{k_b}$以下に解決することはできない。設計上の長所は構造的だ: 構造は$n$ 独立検索 -- 恥ずかしいことに並列で決定論的で、5{,}250$ s for 10^8$ vectors on 64 cores, $3.7\times$ faster than a Matched-recall graph build -- これは強制された3 GiB上限の下でストリームされ、ポータブルアーティファクトは、強制された8GBの予算の中でNVMeから10^8$ vectorsを提供する。飽和グラフベースラインはRAMで6-16\times$高速化され、0.99リコールの検証予算は$n^{0.30}$に増加する。すべての結果は、種子、飽和スイープ、完全な構成を持ち、実行中のマニフェストから生成され、測定された負の結果を含む。意図されたアプリケーションは、ビルドコスト、決定性、メモリフットプリント、あるいは、頻繁に再構築されたコーパス、バッチ類似性ワークロード、制約付きメモリサービスといった、ピークスループット以上のブラックボックスメトリクスを重み付けする。

関連論文リスト

A Spectral Phase Diagram for Binary Few-Shot Classification: Intrinsic Dimensionality, Geometric Saturation, and Representational Diagnosis [0.0]
飽和指数 $S(K) = operatornameerank(widehat_W(K)) / K$ は、プールされたクラス内サンプルの有効ランクとショットカウントとの比を測る。インデックスはサポート機能だけで$O(d3)$ timeで計算可能で、テストラベルやトレーニングされた分類子を必要としない。
論文参考訳（メタデータ） (2026-06-12T16:46:24Z)
Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables [55.952069550106906]
複雑クエリアンサーリング(CQA)は、不完全知識グラフ(KG)上の基本的な知識表現と推論タスクであるここで$mathcalEk$はKGのエンティティセットを表す。既存のベンチマークとメソッドは、個々の変数よりも限界ランクに依存している。我々は、$mathcalEk$を列挙することなく、共同ランキングを近似するフレームワークであるNeural Scalable Symbolic Search (NS3)を提案する。
論文参考訳（メタデータ） (2026-05-25T16:04:57Z)
Represented Is Not Computed: A Causal Test of Candidate Algorithmic Intermediates in a Transformer [0.0]
ベース桁抽出に基づいて訓練されたトランスフォーマーは、ホールドアウトされたナンバーベース交差点で99.83%の精度に達する。スパースサーキットサーチは、プローブが提案するルートよりも遅くに結合するN$、B$、D$ルートを主に分離している。
論文参考訳（メタデータ） (2026-05-21T13:43:25Z)
The Library Theorem: How External Organization Governs Agentic Reasoning Capacity [0.0]
I/O ページとして変換器のコンテキストウィンドウを形式化する。インデックス付き外部メモリを持つツール拡張エージェントは、シーケンシャルスキャンに制限されたエージェントよりも指数関数的に検索コストが低いことを証明した。
論文参考訳（メタデータ） (2026-03-22T15:02:56Z)
Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search [7.168741876130465]
完全なインデックスを再構築することなく$$$パラメータを調整するRP-Tuningを提案する。 RP-Tuningは、4つの公開データセットのDiskANNチューニングを、無視できないオーバーヘッドで最大43タイムで高速化することを示す。
論文参考訳（メタデータ） (2026-02-08T19:34:38Z)
Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文参考訳（メタデータ） (2025-06-30T13:27:39Z)
Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
論文参考訳（メタデータ） (2025-02-16T16:12:01Z)
Data Structures for Density Estimation [66.36971978162461]
p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。また、Acharyaなどのアルゴリズムの改良版も提供します。
論文参考訳（メタデータ） (2023-06-20T06:13:56Z)
List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文参考訳（メタデータ） (2020-11-19T17:21:37Z)
Deep Learning Meets Projective Clustering [66.726500395069]
NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
論文参考訳（メタデータ） (2020-10-08T22:47:48Z)
Faster DBSCAN via subsampled similarity queries [42.93847281082316]
DBSCANは密度に基づくクラスタリングアルゴリズムとして人気がある。本稿では,サブサンプルである$epsilon$-neighborhoodグラフに基づいてクラスタをクラスタ化するSNG-DBSCANを提案する。
論文参考訳（メタデータ） (2020-06-11T18:57:54Z)
A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文参考訳（メタデータ） (2020-06-02T16:38:36Z)

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

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