論文の概要: MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One

• arxiv url: http://arxiv.org/abs/2609.39233v1
• Date: Wed, 30 Sep 2026 08:05:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.42628
• Title: MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One
• Title（参考訳）: MultiTable: 物理負荷要素を1つまで、そして1つまで、より高速なハッシュテーブル
• Abstract要約: 安定なハッシュテーブルは、同じ物理メモリで実質的に高速で、Rustのハッシュブラウン実装でSwissTableよりも柔軟である。 演算は84以上の構成を意味し、どちらも同じ生のバイトをハッシュするとハッシュブラウンのスループットを提供する。 マルチテーブルにはプレーンとフィルタの2つのバリエーションが実装されている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present \emph{multitable} and its Rust reference implementation: a stable hash table both materially faster at equal physical memory and more flexible than the SwissTable in its Rust's hashbrown implementation. As an arithmetic mean over 84 configurations it delivers $\mathbf{2.1\times}$ hashbrown's throughput when both hash the same raw bytes and $\mathbf{1.9\times}$ when hashbrown is keyed on native integers, its best case; on negative lookups alone, $3.2\times$ and $2.9\times$. Multitable reaches \textbf{any physical load factor} up to and \textbf{including one} ($0.9999$ demonstrated), exactly for the requested capacity, compared to hashbrown which doubles at $0.777$ for 4-byte keys and values. At $75\%$ saturation of hashbrown (assumed average case of its rigid ladder) and multitable sized to $0.97$ physical load factor, hashbrown takes $66\%$ more space. The lookup probe count has no cliff as the load factor approaches one. Bucket size, physical load factor, and failure budget are parameters, and the multitable can be grown without rehashing. We implement two variants of multitable: plain and filtered. At equal physical memory on an Apple M2 Pro the filtered multitable leads hashbrown in all $84$ insert, hit, and miss configurations. Multitable is more \textbf{memory-efficient}, at equal mixed-lookup throughput on the map of $4$-byte keys and values the filtered multitable needs up to $12\%$ fewer bytes than hashbrown, and the plain multitable is $18\%$ smaller, holding $\mathbf{22\%}$ more keys in the same memory.
• Abstract（参考訳）: 安定したハッシュテーブルは、同じ物理メモリで実質的に高速で、Rustのハッシュブラウン実装でSwissTableよりも柔軟です。 演算が84以上の設定を意味するので、同じ生のバイトをハッシュした場合に$\mathbf{2.1\times}$hahbrownのスループットと、そのベストケースであるネイティブ整数でhahbrownがキーされる場合の$\mathbf{1.9\times}$、負のルックアップだけで$3.2\times$と$2.9\times$を提供する。 Multitable は 4 バイトのキーと値に対して 0.777$ のハッシュブラウンに比べて、要求されたキャパシティに対して \textbf{any physical load factor} と \textbf{ including one} (0.9999$ demonstrated) に達する。 サイズは75ドル(約7,800円)、サイズは0.97ドル(約6,800円)。 ルックアッププローブ数には、負荷係数が1に近づくため、崖がない。 バッチサイズ、物理的負荷係数、障害予算はパラメータであり、マルチテーブルはリハすることなく成長することができる。 マルチテーブルにはプレーンとフィルタの2つのバリエーションが実装されている。 Apple M2 Proの物理メモリは同じで、フィルターされたマルチテーブルのリードは、84ドル(約8,800円)の挿入、ヒット、ミスの設定をすべてハッシュブラウンする。 Multitable はより \textbf{Memory-efficient} で、4$バイトのキーと値のマップ上の同じ混合ルックアップスループットで、フィルタされた Multitable はハッシュブラウンよりも最大 12\%$ バイト少ない値を必要とし、プレーンな multitable は1800\%$ より小さく、同じメモリに $\mathbf{22\%}$ 以上のキーを保持する。

関連論文リスト

• Memoization Without Keys: Compact, Out-of-Core Tables for Functions of Sorted Arguments [0.0]
  我々は、何も格納しない実装されたメモテーブルについて述べる。 エントリのアドレスは、ソートされた引数自身からクローズドな形式で計算される。 プラケット・ルーシ正規化のメモ化はニュートン法より25ドル-55ドル速い。
  論文  参考訳（メタデータ） (2026-07-29T11:10:59Z)
• Spotlight Attention: Towards Efficient LLM Generation via Non-linear Hashing-based KV Cache Retrieval [67.21678698740267]
  本研究では,クエリやキーの埋め込み分布を最適化するために,非線形ハッシュ関数を利用する新しい手法であるSpotlight Attentionを紹介する。 また、Bradley-Terryランキングに基づく損失を利用して、軽量で安定したトレーニングフレームワークを開発する。
  論文  参考訳（メタデータ） (2025-08-27T10:11:27Z)
• Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields [2.069755423622365]
  AXUハッシュ関数deBRWHashはBernsteinRabin-Winograd(BRW)に基づいている 4-decBRWHashは、数百バイトのメッセージではより高速で、数キロバイトのメッセージ長で約16%のスピードアップを実現している。
  論文  参考訳（メタデータ） (2025-07-09T02:27:33Z)
• 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)
• Pb-Hash: Partitioned b-bit Hashing [21.607059258448594]
  我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。 我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。 一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
  論文  参考訳（メタデータ） (2023-06-28T06:05:47Z)
• 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)

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

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