論文の概要: Authenticated Data Structures for Dynamic Workloads
- arxiv url: http://arxiv.org/abs/2608.25206v1
- Date: Tue, 25 Aug 2026 22:46:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-27 14:15:15.487982
- Title: Authenticated Data Structures for Dynamic Workloads
- Title（参考訳）: 動的ワークロードのための認証データ構造
- Abstract要約: Huffman-Merkle Tree (HMT)は、動的ワークロードのための認証データ構造である。
HMTは2つの相補的なメカニズムを通してアクセススキューを動的に変化させる。
我々はHMTを実装し、実際のデータと比較し、MerkleのPatricia Trie (MPT) ADSとその代替案であるUnified Binary Tree (UBT)と比較する。
- 参考スコア（独自算出の注目度）: 3.1912286225194877
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce the Huffman-Merkle Tree (HMT), an authenticated data structure (ADS) for dynamic workloads where items may differ in access frequencies, and access frequencies can change over time. An ADS allows proving item membership against a short commitment to a large mutable state, with applications including verifiable storage, Internet transparency services, and blockchains. Optimizing ADS performance under continuously changing access frequencies has not been fully addressed before, neither in theory nor in practice. HMT addresses dynamically changing access skew through two complementary mechanisms. The first is a Huffman-coding-based Merkle-tree layout, with a novel extension to support evolving access frequencies. The second is an elastic tiering regime that partitions items across separate trees, such as hot and cold tiers, with adaptive migration between them. The key insight in this approach is to place frequently accessed items closer to the root, while assigning less frequently accessed items to progressively larger and deeper trees. This reduces the overall frequency-weighted access cost. Our scheme is designed to scale to gigabytes of data spanning millions of items. To handle dynamism efficiently, layout updates are applied in batches, access frequencies are tracked using a count-min sketch, and the system employs a tier-promotion cache while exploring multiple tier-migration policies. We implement HMT and compare it on real-world data with Ethereum's Merkle Patricia Trie (MPT) ADS and its proposed replacement, the Unified Binary Tree (UBT). Our evaluation considers two metrics: the amount of hashing per update and access-weighted membership-proof size. The latter captures both item access cost and frequency. We find that the best HMT policy uses about 2.4x and 0.34x less average hash operations than MPT and UBT respectively, and has 0.18x and 0.55x shorter proofs.
- Abstract（参考訳）: 本稿では,Huffman-Merkle Tree (HMT)を紹介した。HMTは動的ワークロードのための認証データ構造(ADS)であり,アクセス周波数が異なる場合があり,アクセス頻度が経時的に変化する可能性がある。
ADSは、検証可能なストレージ、インターネット透過性サービス、ブロックチェーンを含むアプリケーションを含む、大規模な変更可能な状態に対する短いコミットメントに対するアイテムメンバシップの証明を可能にする。
連続的なアクセス周波数変化下でのADS性能の最適化は、理論上も実際においても、これまで完全には解決されていない。
HMTは2つの相補的なメカニズムを通してアクセススキューを動的に変化させる。
ひとつはHuffmanによるコーディングベースのMerkle-treeレイアウトで、進化するアクセス周波数をサポートするための新しい拡張である。
第2の階層構造は、熱い層や冷たい層など、別々の木にまたがってアイテムを分割し、それら間で適応的な移動を行う弾性階層構造である。
このアプローチにおける重要な洞察は、頻繁にアクセスされたアイテムをルートの近くに配置し、アクセスされていないアイテムを徐々に大きく深い木に割り当てることである。
これにより、全体の周波数重み付けアクセスコストが削減される。
私たちのスキームは、数百万のアイテムにまたがるギガバイトのデータにスケールするように設計されています。
ダイナミズムを効率的に処理するために、レイアウト更新をバッチに適用し、アクセス頻度をカウントミンスケッチを用いて追跡し、複数の階層移動ポリシーを探索しながら階層移動キャッシュを使用する。
我々はHMTを実装し、EthereumのMerkle Patricia Trie (MPT) ADSとその代替案であるUnified Binary Tree (UBT)と比較する。
評価では,更新毎のハッシュの量と,アクセス重み付き会員制サイズという2つの指標を検討した。
後者は、アイテムアクセスコストと周波数の両方をキャプチャする。
最高のHMTポリシでは,MPTやUBTよりも平均ハッシュ操作が2.4倍,0.34倍少なくなり,0.18倍,0.55倍の短い証明が得られた。
関連論文リスト
- MESS: Fast and Private Semantic Search on Multi-Graph HNSW [11.990611521434944]
プライバシ,正確性,効率性の3つの特性を持つ検索システムであるMESSを紹介する。
元のベクトルをバイナリコードにマッピングし、ローカリティ・センシティブなハッシュ(LSH)とランダムな応答を適用し、多グラフ階層ナビゲート可能な小型世界(HNSW)インデックスを摂動コード上に構築する。
MESSは、最先端のベースラインよりも最大15.08タイムのレイテンシを実現する。
論文 参考訳（メタデータ） (2026-07-31T03:53:24Z) - A Parametric Memory Head for Continual Generative Retrieval [52.66674234249913]
生成情報検索(GenIR)は、検索を単一のニューラルモデルに統合し、クエリから直接ドキュメント識別子(ドシデント)をデコードする。
逐次適応は、新たに追加された文書の検索を改善するが、以前のスライスの性能は著しく低下することを示す。
本稿では,モジュール型パラメトリックメモリヘッドで適応モデルを拡張するメモリのみの安定化ステージである,後適応メモリチューニング(PAMT)を提案する。
論文 参考訳（メタデータ） (2026-04-25T17:38:51Z) - FastFit: Accelerating Multi-Reference Virtual Try-On via Cacheable Diffusion Models [59.8871829077739]
FastFitは、キャッシュ可能な新しい拡散アーキテクチャに基づいた、高速なマルチ参照仮想試行フレームワークである。
本モデルでは,パラメータのオーバーヘッドを無視して参照特徴符号化をデノナイズ処理から完全に切り離す。
これにより、参照機能は一度だけ計算され、すべてのステップで損失なく再利用される。
論文 参考訳（メタデータ） (2025-08-28T09:25:52Z) - MEM1: Learning to Synergize Memory and Reasoning for Efficient Long-Horizon Agents [84.62985963113245]
我々は,長時間のマルチターンタスクに対して,エージェントが一定のメモリで動作可能な,エンドツーエンドの強化学習フレームワークMEM1を紹介する。
各ターンでMEM1は、メモリ統合と推論を共同でサポートするコンパクトな共有内部状態を更新する。
その結果,MEM1-7Bは16目的のマルチホップQAタスクにおいて,Qwen2.5-14B-Instructと比較してメモリ使用量を3.7倍削減し,3.5倍の性能向上を示す。
論文 参考訳（メタデータ） (2025-06-18T19:44:46Z) - A Compressive Memory-based Retrieval Approach for Event Argument Extraction [18.526784020974024]
イベントアグラメント抽出(EAE)のための圧縮メモリベース検索(CMR)機構を提案する。
提案手法は,3つの公開データセット上での最先端性能を実現する。
論文 参考訳（メタデータ） (2024-09-14T05:51:50Z) - Fast Online Hashing with Multi-Label Projection [15.85793225585693]
本稿では,データベースの小さな部分のバイナリコードのみを更新するFast Online Hashing(FOH)手法を提案する。
実験結果から,提案したFOHは,最先端のベースラインよりも6.28秒少ないクエリ時間で劇的な優位性が得られることが示された。
論文 参考訳（メタデータ） (2022-12-03T03:19:28Z) - Injecting Domain Adaptation with Learning-to-hash for Effective and
Efficient Zero-shot Dense Retrieval [49.98615945702959]
我々は,TAS-B高密度検索器の下流ゼロショット検索精度を向上させるためのLTHおよびベクトル圧縮技術を評価する。
以上の結果から, 従来の研究とは異なり, LTH法はゼロショットTAS-B高密度レトリバーを平均14%のnDCG@10で過小評価できることがわかった。
論文 参考訳（メタデータ） (2022-05-23T17:53:44Z) - MD-CSDNetwork: Multi-Domain Cross Stitched Network for Deepfake
Detection [80.83725644958633]
現在のディープフェイク生成法では、偽画像やビデオの周波数スペクトルに識別的アーティファクトが残されている。
MD-CSDNetwork(MD-CSDNetwork)と呼ばれる新しい手法を提案する。
論文 参考訳（メタデータ） (2021-09-15T14:11:53Z) - MOON: Multi-Hash Codes Joint Learning for Cross-Media Retrieval [30.77157852327981]
クロスメディアハッシュ技術は高い計算効率と低ストレージコストで注目を集めている。
クロスメディア検索のための新しいMultiple hash cOdes jOint learNing法(MOON)を開発した。
論文 参考訳（メタデータ） (2021-08-17T14:47:47Z) - Disentangle Your Dense Object Detector [82.22771433419727]
深層学習に基づく高密度物体検出器はここ数年で大きな成功を収め、ビデオ理解などのマルチメディアアプリケーションにも応用されてきた。
しかし、現在の高密度検出器の訓練パイプラインは、保持できない多くの接続に妥協されている。
そこで本研究では, 簡易かつ効果的な遠心分離機構を設計し, 現在の最先端検出器に統合するDED(Disentangled Dense Object Detector)を提案する。
論文 参考訳（メタデータ） (2021-07-07T00:52:16Z) - Qd-tree: Learning Data Layouts for Big Data Analytics [33.07610112749939]
本稿では、クエリデータルーティングツリー(qd-tree)と呼ばれる新しいフレームワークを提案し、この問題に対処する。
実験により、qd木は現在のブロッキング方式と比較して1桁以上の物理的スピードアップを提供できることが示された。
論文 参考訳（メタデータ） (2020-04-22T23:42:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。