Fugu-MT 論文翻訳(概要): TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead

論文の概要: TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead

arxiv url: http://arxiv.org/abs/2205.05211v5
Date: Tue, 4 Jun 2024 13:24:18 GMT
ステータス: 処理完了
システム内更新日: 2024-06-06 16:52:40.879575
Title: TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead
Title（参考訳）: TreePIR: 高速インデックス化とゼロストレージオーバヘッドを用いたツリーカラー化によるメルクルプロフの効率的なプライベート検索
Authors: Son Hoang Dau, Quang Cao, Rinaldo Gagiano, Duy Huynh, Xun Yi, Phuc Lu Le, Quang-Hung Luu, Emanuele Viterbo, Yu-Chih Huang, Jingge Zhu, Mohammad M. Jalalzai, Chen Feng,
Abstract要約: Batch Private Information Retrieval (Batch-PIR)は、クライアントがデータベースから複数のデータアイテムを格納サーバに公開せずに取得することを可能にする。バッチPIRの既存のアプローチのほとんどは、大きなストレージオーバーヘッドを引き起こすバッチコードに基づいている。木型データベースでは,テキスタイルストレージのオーバーヘッドが実現可能であることを示す。
参考スコア（独自算出の注目度）: 25.255031090404948
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A Batch Private Information Retrieval (batch-PIR) scheme allows a client to retrieve multiple data items from a database without revealing them to the storage server(s). Most existing approaches for batch-PIR are based on batch codes, in particular, probabilistic batch codes (PBC) (Angel et al. S&P'18), which incur large storage overheads. In this work, we show that \textit{zero} storage overhead is achievable for tree-shaped databases. In particular, we develop TreePIR, a novel approach tailored made for private retrieval of the set of nodes along an arbitrary root-to-leaf path in a Merkle tree with no storage redundancy. This type of trees has been widely implemented in many real-world systems such as Amazon DynamoDB, Google's Certificate Transparency, and blockchains. Tree nodes along a root-to-leaf path forms the well-known Merkle proof. TreePIR, which employs a novel tree coloring, outperforms PBC, a fundamental component in state-of-the-art batch-PIR schemes (Angel et al. S&P'18, Mughees-Ren S&P'23, Liu et al. S&P'24), in all metrics, achieving $3\times$ lower total storage and $1.5$-$2\times$ lower computation and communication costs. Most notably, TreePIR has $8$-$160\times$ lower setup time and its polylog-complexity indexing algorithm is $19$-$160\times$ faster than PBC for trees of $2^{10}$-$2^{24}$ leaves.
Abstract（参考訳）: Batch Private Information Retrieval (batch-PIR)スキームにより、クライアントはデータベースから複数のデータアイテムを格納サーバに公開することなく取得することができる。バッチPIRの既存のアプローチのほとんどはバッチコード、特に大きなストレージオーバーヘッドを引き起こす確率的バッチコード(PBC)(Angel et al S&P'18)に基づいている。本研究では,木形データベースのストレージオーバーヘッドが達成可能であることを示す。特に,記憶冗長性のないメルクルツリーにおいて,任意のルート・ツー・リーフ経路に沿ってノードの集合をプライベートに検索する手法であるTreePIRを開発した。この種のツリーは、Amazon DynamoDB、GoogleのCertificate Transparency、ブロックチェーンなど、多くの現実世界のシステムで広く実装されている。ルート・ツー・リーフ・パスに沿ったツリーノードは、よく知られたメルクル証明を形成する。ツリーカラーを採用したTreePIRは、最先端のバッチ-PIRスキーム(Angel et al S&P'18, Mughees-Ren S&P'23, Liu et al S&P'24)の基本コンポーネントであるPBCを、すべてのメトリクスで上回り、総ストレージが3ドル、通信コストが1.5ドル=2ドルである。もっとも注目すべきは、TreePIR のセットアップ時間は 8 ドルから 160 ドルで、そのポリログ-複雑度インデックスアルゴリズムは、$2^{10}$-2^{24}$の木の PBC よりも高速である。

関連論文リスト

Tree-of-Traversals: A Zero-Shot Reasoning Algorithm for Augmenting Black-box Language Models with Knowledge Graphs [72.89652710634051]
知識グラフ(KG)は、信頼性があり、構造化され、ドメイン固有であり、最新の外部知識を提供することで、Large Language Models(LLM)を補完する。そこで本研究では,ゼロショット推論アルゴリズムであるTree-of-Traversalsを導入する。
論文参考訳（メタデータ） (2024-07-31T06:01:24Z)
LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文参考訳（メタデータ） (2024-06-29T05:14:04Z)
End-to-end Feature Selection Approach for Learning Skinny Trees [13.388576838688202]
木アンサンブルにおける特徴選択のための最適化に基づく新しい手法を提案する。 Skinny Treesは、ツリーアンサンブルの機能選択のためのエンドツーエンドツールキットである。
論文参考訳（メタデータ） (2023-10-28T00:15:10Z)
On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
論文参考訳（メタデータ） (2023-06-07T13:30:43Z)
Phylo2Vec: a vector representation for binary trees [0.49478969093606673]
系統樹を模したPhylo2Vecについて紹介する。系統樹を操作および表現するための統一的なアプローチとして機能する。概念実証として、Phylo2Vecを用いて5つの実世界のデータセットの最大推定を行う。
論文参考訳（メタデータ） (2023-04-25T09:54:35Z)
Learning-Augmented B-Trees [11.542679443281411]
本研究は,Treapsを用いたBST(Learning-augmented binary search tree)とB-Trees(B-Trees)を複合優先度で検討する。その結果、各項目の深さが予測重量$w_x$で決定される単純な探索木となる。
論文参考訳（メタデータ） (2022-11-16T22:50:40Z)
On Finding the $K$-best Non-projective Dependency Trees [39.5549669100436]
我々はCamerini et al. (1980) の$K$-bestスパンニングツリーアルゴリズムを単純化する。ルート制約を受けるグラフの$K$-best依存木を復号するアルゴリズムを新たに拡張する。
論文参考訳（メタデータ） (2021-06-01T20:23:41Z)
Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文参考訳（メタデータ） (2021-04-14T18:15:27Z)
Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
論文参考訳（メタデータ） (2020-12-29T18:05:05Z)
Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
文を構文木にパースすることは、NLPの下流アプリケーションに恩恵をもたらす。トランジッションベースは、状態遷移システムでアクションを実行することでツリーを構築する。既存のトランジションベースは主にシフト・リデュース・トランジション・システムに基づいている。
論文参考訳（メタデータ） (2020-10-27T19:19:38Z)
An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
論文参考訳（メタデータ） (2020-10-22T10:59:49Z)

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

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