論文の概要: Memoization Without Keys: Compact, Out-of-Core Tables for Functions of Sorted Arguments
- arxiv url: http://arxiv.org/abs/2609.20276v2
- Date: Mon, 21 Sep 2026 18:17:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 05:09:55.651533
- Title: Memoization Without Keys: Compact, Out-of-Core Tables for Functions of Sorted Arguments
- Title（参考訳）: キーなしのメモ化:Sorted Argumentsの機能のためのコンパクトで外付けのテーブル
- Abstract要約: 我々は、何も格納しない実装されたメモテーブルについて述べる。
エントリのアドレスは、ソートされた引数自身からクローズドな形式で計算される。
プラケット・ルーシ正規化のメモ化はニュートン法より25ドル-55ドル速い。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Memoizing an expensive function of a sorted score vector is a data-structure problem before it is a numerical one: at a billion gridpoints, a hash map or a search tree spends most of its space on keys the grid already determines. We describe an implemented memo table that stores none. An entry's address is computed in closed form from the sorted argument itself, so $N$ values occupy $N$ slots, the argument is recoverable from the index, and the table can be memory-mapped and served from a file larger than RAM. Against a chained hash map it uses $5.7\times$ less memory at $37$M entries and $10.2\times$ less at $1.9$B, answers queries up to $2.9\times$ faster and builds up to $250\times$ faster; on 64 threads its construction needs no coordination; a sharded hash gains only $1.17\times$. Against an open-addressing table with inline keys it is $4$--$7\times$ smaller and $100\times$ faster to build but $1.5\times$ slower to query, a deficit we trace to the $O(d)$ index arithmetic. At $22$ GB on a $16$ GB desktop it serves each query in one disk access, where no key-storing container can be built; and its order-preserving addressing keeps a perturbation workload on the same pages that a hashed layout scatters. The closed form exists because the key set is the multiset combinations, whose index is the combinatorial number system. Memoizing Plackett--Luce normalization runs $25$--$55\times$ faster than Newton's method; memoizing $α$-entmax thresholds does not pay. The contrast says when this structure is worthwhile.
- Abstract（参考訳）: ソートされたスコアベクトルの高価な関数を記憶することは、数値的な問題になる前にデータ構造の問題である: 10億のグリッドポイント、ハッシュマップ、検索ツリーは、既にグリッドが決めているキーにその空間の大部分を費やしている。
我々は、何も格納しない実装されたメモテーブルについて述べる。
エントリのアドレスはソートされた引数自身からクローズドな形式で計算されるので、$N$値は$N$スロットを占有し、引数はインデックスから復元可能であり、テーブルはメモリマップされ、RAMよりも大きいファイルから提供される。
連鎖したハッシュマップに対して、$57\times$メモリを37ドル、$10.2\times$を1.9ドルBで、問合せは$2.9\times$で、ビルドは$250\times$で、64スレッドでは調整を必要とせず、シャードされたハッシュは$1.17\times$でしか得られない。
インラインキーを備えたオープンアドレッシングテーブルに対して、4$--$7\times$小さく100\times$ビルドが速いが、1.5\times$クエリが遅い。
16ドル(約1万2000円)のデスクトップ上では22ドル(約2万2000円)のGBで、1つのディスクアクセスで各クエリを処理し、キー保存コンテナを構築できない。
閉形式は、鍵集合が多重集合結合であり、その指数が組合せ数系であるからである。
Memoizing Plackett--Luce normalization run $25$--55\times$ than Newton's method; memoizing $α$-entmax thresholds not pay。
対照的に、この構造は価値あるものである。
関連論文リスト
- misi: a Metric Inverted Sample Index [0.0]
mii は一般距離空間上の近似近傍探索のための逆インデックスである。
それぞれのオブジェクトは、$k_b$の最も近いサンプルポイントで表現され、サンプル上のプラグ可能なインナーインデックスによって見つかる。
クエリはidf-weighted shared-neighborの投票によって回答され、続いて$C$の候補の正確な検証が行われる。
論文 参考訳（メタデータ） (2026-08-27T17:48:22Z) - Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch [0.0]
アクティベーションチェックポイントは、所定のメモリ予算下でのニューラルネットワークの実行を最小化する。
本稿では,スライディングウインドウトリックとHirschbergのアルゴリズムを組み合わせてピークメモリの削減を行うdp_knapsack_sliding_hirschbergを紹介する。
論文 参考訳（メタデータ） (2026-08-09T14:36:19Z) - Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。
まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。
決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2026-07-21T00:40:59Z) - Min-Max Optimization Requires Exponentially Many Queries [71.85811744604827]
非min-nonconcave 関数 $f$ $[0,1] のクエリ複雑性。
f$ へのクエリとその勾配点が 1 ord$ で指数関数的な点を成さなければならないことを示す。
論文 参考訳（メタデータ） (2026-05-13T17:34:24Z) - ZenBrain: A Neuroscience-Inspired 7-Layer Memory Architecture for Autonomous AI Systems [51.56484100374058]
LongMemEval-500では、ZenBrainは長いコンテキストのオラクルのバイナリ・ジャッジの精度を4.5pp以内と一致させる。
ZenBrainは7層の神経科学にインスパイアされたメモリアーキテクチャである。
論文 参考訳（メタデータ） (2026-04-26T20:39:19Z) - Fast and Optimal Differentially Private Frequent-Substring Mining [2.451701057085567]
ユーザ分散文字列のデータセットが$n$で、各長さが$ell$である場合、重要な問題は、すべての頻繁な呼び出しを識別する方法である。
我々は,空間複雑性を低減しつつ,ほぼ最適な誤差保証を保った新しい$varepsilon$-differentially privateアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-03-10T04:04:52Z) - LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference [87.57291812372848]
我々は、最適なキャッシュ選択をknapsack問題として扱い、計算オーバーヘッドとキャッシュ更新のバランスをとるために蓄積ベースの戦略を用いる。
我々のアルゴリズムの後悔は$O(sqrtMNT)$boundを達成し、バークレーの$O(MNsqrtT)$と比較して$sqrtMN$の係数を改善することを証明している。
問題に依存したバウンダリも提供しています。
論文 参考訳（メタデータ） (2025-09-19T01:39:08Z) - HashAttention: Semantic Sparsity for Faster Inference [95.31739930718116]
本稿では,HashAttention,framing pivotal token Identificationを推薦問題として紹介する。
トークン1個あたり32ビットの補助メモリしか必要とせず、最小品質の損失を最小限に抑えられるため、最大16タイムで使用されるトークンを削減できる。
A100 GPUでは、HashAttentionを組み込むことで、GPT-FASTで4.3times$、FlashDecodeで2.54times$、GPT-FASTで最大3.12times$高スループットを実現している。
論文 参考訳（メタデータ） (2024-12-19T02:34:15Z) - LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Invertible Bloom Lookup Tables with Less Memory and Randomness [23.724300017513574]
Invertible Bloom Lookup Tables (IBLT) は、セット和解プロトコル、エラー訂正符号、高度な暗号プリミティブの設計に応用されている。
IBLTは同時に空間効率が良く、ランダム性が低い新しい構成を提案する。
k$ の独立ハッシュ関数 $h:U to [Cn]$ for some enough large constant $C$ guarantees with probability $1 - 2-Omega(k)$ that least $n/2$ key will have a unique hash value。
論文 参考訳（メタデータ） (2023-06-13T07:15:02Z) - SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor
Search [39.361122198195076]
本稿では,SPANNというメモリディスクハイブリッドインデックスと検索システムを提案する。
ポストリストのセントロイドポイントをメモリに、大きなポストリストをディスクに格納する。
リコール@1とリコール@10はわずか1ミリ秒で、メモリは32GBだ。
論文 参考訳（メタデータ） (2021-11-05T06:28:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。