論文の概要: New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage
- arxiv url: http://arxiv.org/abs/2504.20888v1
- Date: Tue, 29 Apr 2025 16:05:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-02 19:15:54.975477
- Title: New Capacity Bounds for PIR on Graph and Multigraph-Based Replicated Storage
- Title（参考訳）: グラフ・マルチグラフ・リプリケートストレージにおけるPIRの新しい容量境界
- Authors: Xiangliang Kong, Shreya Meel, Thomas Jacob Maranzatto, Itzhak Tamo, Sennur Ulukus,
- Abstract要約: グラフベースおよびマルチグラフベースの複製システムにおけるプライベート情報検索(PIR)の問題について検討する。
このような系に対するPIR容量の上限を導出し、これらの境界に近づくPIRスキームを構築する。
- 参考スコア（独自算出の注目度）: 39.51026717015587
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of private information retrieval (PIR) in both graph-based and multigraph-based replication systems, where each file is stored on exactly two servers, and any pair of servers shares at most $r$ files. We derive upper bounds on the PIR capacity for such systems and construct PIR schemes that approach these bounds. For graph-based systems, we determine the exact PIR capacity for path graphs and improve upon existing results for complete bipartite graphs and complete graphs. For multigraph-based systems, we propose a PIR scheme that leverages the symmetry of the underlying graph-based construction, yielding a capacity lower bound for such multigraphs. Furthermore, we establish several general upper and lower bounds on the PIR capacity of multigraphs, which are tight in certain cases.
- Abstract（参考訳）: 本稿では,グラフベースとマルチグラフベースのレプリケーションシステムにおいて,各ファイルが正確に2つのサーバに格納され,任意のサーバが最大$r$ファイルを共有する,プライベート情報検索(PIR)の問題について検討する。
このような系に対するPIR容量の上限を導出し、これらの境界に近づくPIRスキームを構築する。
グラフベースのシステムでは、パスグラフの正確なPIR容量を決定し、完全二部グラフと完全グラフの既存の結果を改善する。
マルチグラフベースシステムでは、基礎となるグラフベース構築の対称性を利用して、そのようなマルチグラフに対してキャパシティを低くするPIRスキームを提案する。
さらに,多重グラフのPIR容量の上限値と下限値の設定も行なっており,これは特定の場合において厳密である。
関連論文リスト
- Private Information Retrieval for Graph-based Replication with Minimal Subpacketization [3.795745240553126]
グラフベース複製データベースにおける情報理論的プライベート情報検索のための最小サブパッケージ化方式を新たに設計する。
グラフベースのレプリケーションでは、システムは$N$サーバ間で複製された$K$ファイルで構成され、グラフには$N$ verticesと$K$ edgeがある。
クライアントは、クエリ応答プロトコルを介して、各サーバから所望のファイルのインデックスをプライベートに保ちながら、1つの所望のファイルを検索したい。
論文 参考訳（メタデータ） (2026-01-15T00:34:27Z) - Effect of Full Common Randomness Replication in Symmetric PIR on Graph-Based Replicated Systems [43.914623898157856]
データベースの複製を単純なグラフでモデル化した環境で、対称なプライベート情報検索の問題を再考する。
メッセージとは独立して、すべてのサーバに共通するランダム性を共有させます。
所望シンボル数とダウンロードシンボル数の最大比であるSPIR容量の改善を定量化する。
論文 参考訳（メタデータ） (2025-10-29T17:40:40Z) - Symmetric Private Information Retrieval (SPIR) on Graph-Based Replicated Systems [35.16231062731263]
単純なグラフでモデル化された複製されたデータベース上の対称プライベート情報検索。
本研究では,SPIRを実現するのに必要なサーバ側の共通乱数性も,そのグラフに従ってサーバに複製されるような設定について考察する。
論文 参考訳（メタデータ） (2025-07-23T17:51:08Z) - Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
SPLIT-RAGは、質問駆動セマンティックグラフ分割と協調サブグラフ検索による制限に対処するマルチエージェントRAGフレームワークである。
革新的なフレームワークは、まずリンク情報のセマンティック分割を作成し、次にタイプ特化知識ベースを使用してマルチエージェントRAGを実現する。
属性対応グラフセグメンテーションは、知識グラフを意味的に一貫性のあるサブグラフに分割し、サブグラフが異なるクエリタイプと整合することを保証する。
階層的なマージモジュールは、論理的検証を通じて、部分グラフ由来の解答間の矛盾を解消する。
論文 参考訳（メタデータ） (2025-05-20T06:44:34Z) - RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
完全なRAGパイプラインをシームレスに統合するモジュラーフレームワークであるRAG-on-Graphs Library(RGL)を紹介した。
RGLは、さまざまなグラフフォーマットをサポートし、必須コンポーネントの最適化実装を統合することで、重要な課題に対処する。
評価の結果,RGLはプロトタイピングプロセスの高速化だけでなく,グラフベースRAGシステムの性能や適用性の向上も図っている。
論文 参考訳（メタデータ） (2025-03-25T03:21:48Z) - Private Information Retrieval on Multigraph-Based Replicated Storage [39.51026717015587]
多重グラフを用いた複製システムにおけるプライベート情報検索問題について考察する。
我々の目標は、$r$-multigraphのPIR容量の上下境界を確立することです。
論文 参考訳（メタデータ） (2025-01-29T18:48:22Z) - Data-Adaptive Graph Framelets with Generalized Vanishing Moments for
Graph Signal Processing [2.039632659682125]
本稿では,階層的分割に基づく局所化サポート付きグラフ上でのタイトなフレームレットシステム構築のためのフレームワークを提案する。
我々の構成は、分割木に基づく非常に一般的なパラメタライズドグラフフレームレットシステムを提供する。
学習したグラフフレームレットシステムは,非線形近似および復号化タスクにおいて優れた性能を発揮することを示す。
論文 参考訳（メタデータ） (2023-09-07T07:49:43Z) - MultiSAGE: a multiplex embedding algorithm for inter-layer link
prediction [0.0]
MultiSAGEはGraphSAGEアルゴリズムの一般化であり、複数のネットワークを埋め込むことができる。
我々は、MultiSAGEが層内接続と層間接続の両方を再構築でき、GraphSAGEより優れていることを示す。
論文 参考訳（メタデータ） (2022-06-24T08:50:55Z) - Long Range Graph Benchmark [32.317725340138104]
単にワンホップメッセージパッシングに頼るMP-GNNは、既存のグラフベンチマークでよく使われる。
ベースラインのGNNとGraph Transformerネットワークの両方をベンチマークし、長距離依存をキャプチャするモデルがこれらのタスクにおいて著しく優れていることを検証した。
論文 参考訳（メタデータ） (2022-06-16T13:33:22Z) - MultiBiSage: A Web-Scale Recommendation System Using Multiple Bipartite
Graphs at Pinterest [53.3951260443916]
グラフ畳み込みネットワーク(GCN)はグラフ構造とノードの特徴を効率的に統合し、高品質なノード埋め込みを学習する。
Pinterestでは、Pin-Boardグラフからピン埋め込みを学習するデータ効率のGCNであるPinSageを開発し、デプロイしました。
多様な相互作用を捉えたグラフ上でディープラーニングモデルをトレーニングすることで、高品質なピン埋め込みを学習できることを示す。
論文 参考訳（メタデータ） (2022-05-21T20:04:46Z) - Graph Pooling for Graph Neural Networks: Progress, Challenges, and
Opportunities [128.55790219377315]
グラフニューラルネットワークは多くのグラフレベルのタスクの主要なアーキテクチャとして登場した。
グラフプーリングは、グラフ全体の全体的グラフレベル表現を得るためには不可欠である。
論文 参考訳（メタデータ） (2022-04-15T04:02:06Z) - Diversified Multiscale Graph Learning with Graph Self-Correction [55.43696999424127]
2つのコア成分を組み込んだ多次元グラフ学習モデルを提案します。
情報埋め込みグラフを生成するグラフ自己補正(GSC)機構、および入力グラフの包括的な特性評価を達成するために多様性ブースト正規化(DBR)。
一般的なグラフ分類ベンチマークの実験は、提案されたGSCメカニズムが最先端のグラフプーリング方法よりも大幅に改善されることを示しています。
論文 参考訳（メタデータ） (2021-03-17T16:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。