論文の概要: Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields

• arxiv url: http://arxiv.org/abs/2507.06490v1
• Date: Wed, 09 Jul 2025 02:27:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-10 17:37:43.440522
• Title: Vectorised Hashing Based on Bernstein-Rabin-Winograd Polynomials over Prime Order Fields
• Title（参考訳）: 素数体上のベルンシュタイン-ラビン-ウィノグラード多項式に基づくベクトルハッシュ
• Authors: Kaushik Nath, Palash Sarkar,
• Abstract要約: AXUハッシュ関数deBRWHashはBernsteinRabin-Winograd(BRW)に基づいている 4-decBRWHashは、数百バイトのメッセージではより高速で、数キロバイトのメッセージ長で約16%のスピードアップを実現している。
• 参考スコア（独自算出の注目度）: 3.330229314824913
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the new AXU hash function decBRWHash, which is parameterised by the positive integer $c$ and is based on Bernstein-Rabin-Winograd (BRW) polynomials. Choosing $c>1$ gives a hash function which can be implemented using $c$-way single instruction multiple data (SIMD) instructions. We report a set of very comprehensive hand optimised assembly implementations of 4-decBRWHash using avx2 SIMD instructions available on modern Intel processors. For comparison, we also report similar carefully optimised avx2 assembly implementations of polyHash, an AXU hash function based on usual polynomials. Our implementations are over prime order fields, specifically the primes $2^{127}-1$ and $2^{130}-5$. For the prime $2^{130}-5$, for avx2 implementations, compared to the famous Poly1305 hash function, 4-decBRWHash is faster for messages which are a few hundred bytes long and achieves a speed-up of about 16% for message lengths in a few kilobytes range and improves to a speed-up of about 23% for message lengths in a few megabytes range.
• Abstract（参考訳）: 我々は、正の整数$c$でパラメータ化され、Bernstein-Rabin-Winograd (BRW)多項式に基づく新しいAXUハッシュ関数deBRWHashを導入する。 c>1$を選択すると、$c$-way single instruction multiple data (SIMD)命令を使って実装できるハッシュ関数が提供される。 最新のIntelプロセッサで利用可能なavx2 SIMD命令を用いた4-decBRWHashの包括的手動最適化アセンブリ実装について報告する。 また,通常の多項式をベースとしたAXUハッシュ関数であるpolyHashのavx2アセンブリ実装についても検討した。 我々の実装は素数体上にあり、具体的には素数 2^{127}-1$ と 2^{130}-5$ である。 avx2実装の場合、有名なPoly1305ハッシュ関数と比較して、プライマリの$2^{130}-5$では、4-decBRWHashは数百バイトのメッセージに対してより高速で、数キロバイトのメッセージ長で約16%のスピードアップを実現し、数メガバイトのメッセージ長で約23%のスピードアップを実現している。

関連論文リスト

• 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)
• A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
  Byte-Pairimation (BPE) は、当初圧縮法として考案されたものの、NLPでデータをトークン化するために使われる一般的なアルゴリズムである。 我々は、ランタイムの複雑さを$mathcalOleft(N log Mright)$から$mathcalOleft(N log Mright)$に改善するBPEのより高速な実装を提供しています。
  論文  参考訳（メタデータ） (2023-06-29T10:29:23Z)
• Pb-Hash: Partitioned b-bit Hashing [21.607059258448594]
  我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。 我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。 一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
  論文  参考訳（メタデータ） (2023-06-28T06:05:47Z)
• Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling [37.6593006747285]
  Minwise hashing (MinHash) は、大規模な検索および学習アプリケーションで広く使われている標準アルゴリズムである。 1つの置換ハッシュ(OPH)は、データベクトルを$K$ binに分割し、各bin内でハッシュ値を生成するMinHashの効率的な代替手段である。 我々は, DP-OPH-fix, DP-OPH-re, DP-OPH-randの3つの変種を用いたDP-OPHフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-06-13T10:38:12Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with Circulant Permutations [25.356048456005023]
  我々は,C-MinHashの基本的な考え方を取り入れて,一置換ハッシュの精度を向上させることを提案する。 ジャカード類似度の推定分散は、既存の(同定された) OPH 法よりも厳密に小さいことを示すことができる。
  論文  参考訳（メタデータ） (2021-11-18T06:52:15Z)
• C-MinHash: Rigorously Reducing $K$ Permutations to Two [25.356048456005023]
  MinHash (Minwise hashing) は、大量のバイナリ (0/1) データにおける Jaccard (resemblance) の類似性を近似するために、ランダムハッシュを生成するための重要かつ実用的なアルゴリズムである。 我々は、bf Circulant MinHash (C-MinHash)を提案する。
  論文  参考訳（メタデータ） (2021-09-07T21:06:33Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• DartMinHash: Fast Sketching for Weighted Sets [0.5584060970507505]
  重み付きハッシュは、類似性探索や大規模カーネルマシンに応用した標準的な次元削減手法である。 mathbbR_geq 0d$の重み付き集合を$xとし、期待時間に$k$独立ミンハッシュを計算する単純なアルゴリズムを導入する。
  論文  参考訳（メタデータ） (2020-05-23T14:59:25Z)

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

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